Palindrome Number
The shape of the problem
Return true iff a non-negative integer reads the same forward and backward. Negative numbers are never palindromes (the leading `-` has no pair).
Signals to notice
Brute force first
Convert to string and compare to its reverse. O(d) but allocates a string.
The key insight
You do not need the full reversed number. For a palindrome the first half equals the reversed second half, so you can stop as soon as the halves meet.
Trace it on x=121
x=121 reversed=0 x=12 reversed=1 (pulled digit 1) x=1 reversed=12 (pulled digit 2) reversed(12) >= x(1) → stop compare x(1) == reversed/10(1) → true
What must stay true
At every iteration, `reversed` holds the reverse of the digits already consumed, and `x` holds the digits not yet consumed. The palindrome condition is equivalent to "the two halves meet and agree".
Shape of the loop
if x < 0 or (x % 10 == 0 and x != 0): return false reversed = 0 while x > reversed: reversed = reversed*10 + x%10 x //= 10 return x == reversed or x == reversed // 10
Pseudocode only — the full worked solution lives in the Solution tab.
Easy way to go wrong
Handling odd-length numbers. When the digit count is odd, `reversed` will be exactly one digit longer than `x` at the stopping point — compare `x` to `reversed/10`, not to `reversed`.