Code Implementation

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

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

class Solution {
    public boolean isPalindrome(int x) {
        if (x < 0 || (x % 10 == 0 && x != 0)) {
            return false;
        }
        int reverted = 0;
        while (x > reverted) {
            reverted = reverted * 10 + x % 10;
            x /= 10;
        }
        return x == reverted || x == reverted / 10;
    }
}
      

var isPalindrome = function(x) {
    if (x < 0 || (x % 10 === 0 && x !== 0)) return false;
    let reverted = 0;
    while (x > reverted) {
        reverted = reverted * 10 + x % 10;
        x = Math.floor(x / 10);
    }
    return x === reverted || x === Math.floor(reverted / 10);
};
      

Problem Description

Given an integer x, determine whether it is a palindrome. An integer is a palindrome when it reads the same backward as forward.

• Return true if x is a palindrome integer, otherwise return false.
• Negative numbers are not palindromes by definition.
• Leading zeros are not allowed unless the number is 0 itself.
• Constraints: The input is a 32-bit signed integer.

For example:

• x = 121 → true (since 121 read backward is 121)
• x = -121 → false (since -121 read backward is 121-, not equal)
• x = 10 → false (since 10 read backward is 01)

Thought Process

The first idea is to convert the integer to a string and check if the string reads the same backward as forward. This is simple but not optimal, as it uses extra space for the string.

To optimize, we consider how to compare the digits of the number directly, without converting to a string. We can extract digits from the end and compare them to the digits at the start.

A naive approach would be to reverse the whole number and compare it to the original. However, this may cause integer overflow for very large numbers.

To avoid overflow and unnecessary work, we can reverse only half of the digits and compare them to the remaining half. This is more efficient and safe for all valid inputs.

Solution Approach

Here is the step-by-step algorithm:

1. Handle special cases:
   • If x is negative, it cannot be a palindrome (since the minus sign only appears at the front).
   • If x ends with 0 (but is not 0), it cannot be a palindrome (e.g., 10 becomes 01).
2. Reverse half of the number:
   • Initialize reverted as 0.
   • While x > reverted:
     • Take the last digit from x (x % 10) and add it to reverted (after multiplying reverted by 10).
     • Remove the last digit from x using integer division by 10.
3. Check for palindrome:
   • When the loop ends, x will have the first half of the digits, and reverted will have the second half (reversed).
   • If the number of digits is even, x should equal reverted.
   • If the number of digits is odd, the middle digit doesn't matter, so x should equal reverted // 10 (removing the middle digit).

This approach avoids extra space and integer overflow.

Example Walkthrough

Let's consider x = 1221:

• Initial: x = 1221, reverted = 0
• First iteration: reverted = 0 * 10 + 1221 % 10 = 1, x = 1221 // 10 = 122
• Second iteration: reverted = 1 * 10 + 122 % 10 = 12, x = 122 // 10 = 12
• Now x = 12, reverted = 12. The loop ends since x is not greater than reverted.
• Since x == reverted, the number is a palindrome.

For an odd-digit number, e.g., x = 12321:

• After reversing half: x = 12, reverted = 123
• Now x == reverted // 10 (12 == 12), so it's a palindrome.

Time and Space Complexity

• Brute-force (string conversion):
  • Time: O(n), where n is the number of digits (since we process each character).
  • Space: O(n), for the string representation.
• Optimized (half reverse):
  • Time: O(log₁₀ x), since we process half the digits.
  • Space: O(1), as we only use a few integer variables.

The optimized approach is both faster and uses less memory.

Summary

The palindrome number problem is efficiently solved by reversing only half of the digits and comparing them to the remaining half. This approach avoids extra space and potential overflow, making it optimal. Key insights include handling negative numbers and trailing zeros, and recognizing that only half the digits need to be processed. The solution is both elegant and practical for large integers.