Palindrome Number Solution

Problem

Determine whether a given integer reads the same forwards and backwards. Negative numbers are never palindromes. A single digit is always a palindrome.

Input: x = 121
Output: true
Explanation: 121 reversed is still 121.

Counter-example: x = -121 → false because the negative sign means the number can't read the same in both directions. Similarly, x = 10 → false because its reversal would start with a leading zero.

Intuition

Reading a number backwards is the core challenge. The simplest way is to convert to a string and compare it to its reverse. The smarter approach avoids any string allocation: instead of reversing the entire number (which risks integer overflow), reverse only the back half of the digits and compare it against the front half — when the reversed portion catches up to or exceeds the remaining front portion, you've processed exactly half the digits.

Approach 1 — String Conversion

Convert the number to a string and check whether the string equals its own reverse. Negative numbers short-circuit immediately.

Return false if x is negative.
Convert x to a string s.
Compare s to its reversed form.
Return true if they match.

1def isPalindrome(x: int) -> bool:
2    if x < 0:
3        return False
4    digits = str(x)
5    return digits == digits[::-1]

Time: O(log n) — the string has as many characters as there are digits in x.
Space: O(log n) — the string (and its reversed copy) each hold all the digits.

Approach 2 — Reverse the Second Half

Avoid string allocation entirely by building the reversed second half digit-by-digit. Stop as soon as the reversed portion is at least as large as the remaining front portion. Handle odd-length numbers by stripping the middle digit from the reversed half.

Return false if x is negative, or if x ends in 0 but isn't 0 itself (a number starting with 0 can't be a palindrome).
Initialize reversed_half = 0.
While reversed_half < x: peel the last digit of x onto reversed_half, then truncate x.
After the loop, x holds the front half and reversed_half holds the reversed back half.
Return true if they're equal (even digit count) or if x == reversed_half // 10 (odd digit count, discarding the middle digit).

1def isPalindrome(x: int) -> bool:
2    if x < 0 or (x % 10 == 0 and x != 0):
3        return False
4    reversed_half = 0
5    while reversed_half < x:
6        reversed_half = reversed_half * 10 + x % 10  # peel last digit onto reversed half
7        x //= 10                                      # shrink the front half
8    # even length: front == reversed back; odd length: middle digit sits in reversed_half
9    return x == reversed_half or x == reversed_half // 10

Time: O(log n) — only half the digits are processed, but asymptotically still O(log n).
Space: O(1) — only two integer variables regardless of input size.

Complexity Summary

Approach	Time	Space	When to use
String Conversion	O(log n)	O(log n)	When clarity matters more than memory
Reverse Second Half	O(log n)	O(1)	When the problem disallows string conversion or memory is constrained

Common Mistakes

Forgetting that negative numbers are never palindromes — the minus sign has no pair on the right side, so short-circuit as soon as x < 0.
Not handling multiples of 10 (other than 0) — a number like 10 or 100 ends in zero, but no integer representation starts with zero, so these can't be palindromes; the check x % 10 == 0 && x != 0 catches this before the loop.
Reversing the entire number instead of half — reversing all digits risks integer overflow for large inputs (e.g., a 10-digit number reversed may exceed INT_MAX); stopping at the midpoint avoids this entirely.
Getting the loop termination wrong — the loop must run while reversedHalf < x; stopping too early leaves too few digits in reversedHalf, while stopping too late (e.g., <=) over-peels on even-length numbers.
Forgetting the odd-length check — for a 3-digit palindrome like 121, the loop exits with x=1 and reversedHalf=12; checking only x == reversedHalf would return false, so the x == reversedHalf // 10 branch is essential.

Palindrome Number — Solution