Problem
Given an integer x, return true if x is a palindrome (reads the same backward as forward).
Example
Input: 121
Output: trueInput: -121
Output: false
Reads as 121- from right to left.Solution
Reverse the second half of the number and compare with the first half. Saves space vs converting to string.
def is_palindrome(x):
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);
}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;
}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;
}Complexity
- Time: O(log n)
- Space: O(1)
Explanation
We only reverse half the digits. When the reversed half meets or exceeds the remaining first half, we know we processed enough. For odd-length numbers, the middle digit ends up in rev, so we divide it out.
Comments
Join the discussion. Got a question, found an issue, or want to share your experience?