Palindrome Number

How it works

Reversing the entire number risks integer overflow. A clever optimization is to reverse only the second half of the number and compare it to the first half.

We keep extracting digits from the end and building the reversed half until the reversed half is greater than or equal to the remaining number. At that point, we have processed half (or just past half) of the digits.

Steps

1. Handle edge cases: negative numbers and numbers ending in 0 (except 0 itself) are not palindromes.
2. Initialize rev = 0.
3. While x > rev:
   • Extract the last digit of x and append it to rev.
   • Remove the last digit from x.
4. After the loop, compare x == rev (even length) or x == rev / 10 (odd length, where the middle digit is in rev).
5. Return true if either condition holds.

Complexity

• Time complexity: O(n)
• Space complexity: O(1)

Where n is the number of digits in the given integer.

Things to watch for

Forgetting Negative Numbers Are Not Palindromes

Negative numbers have a minus sign at the front, so they can never be palindromes (e.g., -121 reads as 121- backwards). Failing to handle negative numbers as an early return case leads to incorrect results or issues with modulo operations on negative values.

Not Handling Numbers Ending in Zero

Numbers ending in zero (except zero itself) cannot be palindromes because leading zeros are not allowed in integers. For example, 10 would need to be 01 reversed, which is not a valid representation. The half-reversal approach fails on these cases without explicit handling, as the loop condition x > rev may never be satisfied correctly.

class Solution:
    def isPalindrome(self, x: int) -> bool:
        if x < 0 or (x != 0 and x % 10 == 0):
            return False

        rev = 0
        while x > rev:
            rev = (rev * 10) + (x % 10)
            x //= 10

        return x == rev or x == rev // 10

class Solution {
public:
    bool isPalindrome(int x) {
        if (x < 0 || (x != 0 && x % 10 == 0)) {
            return false;
        }

        int rev = 0;
        while (x > rev) {
            rev = rev * 10 + x % 10;
            x /= 10;
        }

        return x == rev || x == rev / 10;
    }
};