Palindrome Number
Reverse the lower half — equals (or with-middle-digit equals) the upper half.
3 min read
Problem#
Return true iff x reads the same forward and backward. Negative numbers are never palindromes.
Examples#
121→true.-121→false;10→false.
Constraints#
-2^31 <= x <= 2^31 - 1.
Approach#
Negatives and non-zero numbers ending in 0 are out. Otherwise, build the reverse of the right half by repeatedly peeling digits, stopping once reversed >= remaining left half. Palindrome iff left == reversed (even length) or left == reversed / 10 (odd length).
Solution#
class Solution {public: bool isPalindrome(int x) { if (x < 0 || (x % 10 == 0 && x != 0)) return false; int rev = 0; while (x > rev) { rev = rev * 10 + x % 10; x /= 10; } return x == rev || x == rev / 10; }};func isPalindrome(x int) bool { if x < 0 || (x%10 == 0 && x != 0) { return false } rev := 0 for x > rev { rev = rev*10 + x%10 x /= 10 } return x == rev || x == rev/10}class Solution: def isPalindrome(self, x: int) -> bool: if x < 0 or (x % 10 == 0 and x != 0): return False rev = 0 while x > rev: rev = rev * 10 + x % 10 x //= 10 return x == rev or x == rev // 10function isPalindrome(x) { if (x < 0 || (x % 10 === 0 && x !== 0)) return false; let rev = 0; while (x > rev) { rev = rev * 10 + (x % 10); x = Math.floor(x / 10); } return x === rev || x === Math.floor(rev / 10);}class Solution { public boolean isPalindrome(int x) { if (x < 0 || (x % 10 == 0 && x != 0)) return false; int rev = 0; while (x > rev) { rev = rev * 10 + x % 10; x /= 10; } return x == rev || x == rev / 10; }}function isPalindrome(x: number): boolean { if (x < 0 || (x % 10 === 0 && x !== 0)) return false; let rev = 0; while (x > rev) { rev = rev * 10 + (x % 10); x = Math.floor(x / 10); } return x === rev || x === Math.floor(rev / 10);}Editorial#
Reversing only the lower half avoids overflow even for INT_MAX — we never need to fit the full reversed number into an int. The loop terminates exactly when we’ve consumed half the digits.
Complexity#
- Time:
O(log10 n). - Space:
O(1).
Concept revision#
Related#