Palindrome Number
Test whether an integer reads the same both ways by reversing only half of its digits
Problem Statement
Given an integer x, return true if it is a palindrome — that is, if it reads the same forwards and backwards.
The interesting version of this problem forbids converting the number to a string.
Input: 121 → true
Input: -121 → false ("-121" reversed is "121-")
Input: 10 → false ("10" reversed is "01")
Input: 0 → trueIntuition
The quick observations
Two cases are decided before any real work:
Negatives and trailing zeros
Negative numbers are never palindromes. The minus sign is at the front and cannot appear at the back.
Any number ending in 0 is a palindrome only if it is 0 itself. A palindrome ending in 0 would have to start with 0, and no multi-digit integer does.
Reversing digits without strings
The core loop peels digits from the right and rebuilds them on the left:
x = 121, reversed = 0
x % 10 = 1 → reversed = 0 × 10 + 1 = 1, x = 12
x % 10 = 2 → reversed = 1 × 10 + 2 = 12, x = 1
x % 10 = 1 → reversed = 12 × 10 + 1 = 121, x = 0x % 10 takes the last digit; x // 10 removes it; reversed * 10 + digit appends on the other side.
The key insight — reverse only half
Reversing the entire number risks overflow in fixed-width languages, and does more work than necessary.
Instead, stop when the reversed half becomes at least as large as what remains of x. At that point you have consumed exactly half the digits, and:
- Even length →
x == reversed - Odd length →
x == reversed // 10(drop the middle digit, which is shared and always matches itself)
Watch it run
Approach
Reject the easy cases
x < 0 → false. x != 0 and x % 10 == 0 → false.
Peel digits until the halves meet
While x > reversed: move the last digit of x onto reversed.
Compare, allowing for an odd middle digit
Return x == reversed or x == reversed // 10.
Solution
def is_palindrome(x: int) -> bool:
"""True if the integer x reads the same both ways. No string conversion."""
# Negatives never work; a trailing zero only works for 0 itself.
if x < 0 or (x != 0 and x % 10 == 0):
return False
reversed_half = 0
while x > reversed_half:
reversed_half = reversed_half * 10 + x % 10
x //= 10
# Even length: x == reversed_half.
# Odd length: the middle digit sits in reversed_half — drop it.
return x == reversed_half or x == reversed_half // 10The string version, if it were allowed:
def is_palindrome_string(x: int) -> bool:
s = str(x)
return s == s[::-1]Use integer division, not `/`
Python: x / 10 produces a float, which breaks the digit arithmetic. Use //.
TypeScript: x / 10 produces a decimal. Since x is non-negative inside the loop, Math.floor is correct; Math.trunc would be equivalent here.
Complexity Analysis
Time Complexity
O(log₁₀ n)
Space Complexity
O(1)
- Time — the loop runs once per digit, and a number
nhas aboutlog₁₀ ndigits. Even a 32-bit maximum takes only 10 iterations. - Space — two integers. The string version is also
O(log n)time but allocatesO(log n)space for the string and its reverse.
Edge Cases
Related Problems
- Valid Palindrome — the string version, with characters to skip
- Reverse Linked List — reversal as a structural operation
- Roman to Integer — another digit-and-symbol manipulation problem