Palindrome Number

Share

Given an integer x, return true if x is a palindrome, and false otherwise. An integer is a palindrome when it reads the same forward and backward. Solve it without converting the integer to a string.

Example 1
Input: x = 121
Output: true
Explanation: 121 reads as 121 from left to right and from right to left.
Example 2
Input: x = -121
Output: false
Explanation: From left to right it reads -121. From right to left it reads 121-. Not a palindrome.
Example 3
Input: x = 10
Output: false
Explanation: Reads 01 from right to left, which is not 10.

Solution Approach

Negative numbers and numbers ending in 0 (except 0 itself) cannot be palindromes. We reverse only the second half of the number and compare it with the first half, avoiding any overflow issues.

  • Return false for negatives or numbers ending in 0 (except 0).
  • Reverse the second half digit by digit: reversed = reversed * 10 + x % 10, x /= 10.
  • Stop when reversed >= x (we've processed half the digits).
  • For even-length: check x == reversed. For odd-length: check x == reversed / 10.
Java
class Solution {
    public boolean isPalindrome(int x) {
        if (x < 0 || (x % 10 == 0 && x != 0)) return false;
        int reversed = 0;
        while (x > reversed) {
            reversed = reversed * 10 + x % 10;
            x /= 10;
        }
        return x == reversed || x == reversed / 10;
    }
}
Complexity Analysis:

Time complexity: O(log x). We process half the digits.
Space complexity: O(1). Constant extra space.