Math & Number Theory - Palindrome Number

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.

Input: x = 121
Output: true
Explanation: 121 reads as 121 from left to right and from right to left.

Input: x = -121
Output: false
Explanation: From left to right it reads -121. From right to left it reads 121-. Not a palindrome.

Input: x = 10
Output: false
Explanation: Reads 01 from right to left, which is not 10.

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.

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.