Palindrome Number
Last Updated: March 28, 2026
Understanding the Problem
We need to check whether an integer reads the same forwards and backwards. At first, this feels like a string problem in disguise: convert the number to a string and check if the string is a palindrome. That works, but the follow-up explicitly asks us to avoid string conversion.
So the real challenge is: how do you reverse or compare digits of a number using only arithmetic? The key observation is that you can extract digits from the end of a number using modulo and division, and you can build a reversed number digit by digit. If the reversed number equals the original, it's a palindrome.
There's also a quick shortcut worth noticing: negative numbers are never palindromes (the minus sign doesn't appear at the end), and numbers ending in 0 can't be palindromes unless the number itself is 0.
Key Constraints:
-2^31 <= x <= 2^31 - 1→ The input is a single 32-bit integer. No array to iterate over, so we're looking at O(log n) or O(1) approaches where n is the value of x (the number of digits is proportional to log10(x)).- The follow-up asks for a non-string solution, hinting that the interviewer values a mathematical approach.
Approach 1: String Conversion
Intuition
The most natural approach: convert the integer to a string and check if the string reads the same forwards and backwards. This is what most people would try first, and it's perfectly valid in a real interview as a starting point.
You can either reverse the string and compare, or use two pointers from both ends moving inward. Both are straightforward.
Algorithm
- Convert the integer to its string representation.
- Use two pointers: one at the start, one at the end.
- Compare characters at both pointers. If they ever differ, return false.
- Move the pointers inward and repeat until they meet.
- If all characters matched, return true.
Example Walkthrough
Code
- Time Complexity: O(d) where d is the number of digits. We convert the number to a string (O(d)) and then compare at most d/2 pairs of characters.
- Space Complexity: O(d). We create a string representation of the number, which uses space proportional to the number of digits.
This approach works but allocates O(d) extra memory for the string. What if we could reverse the digits using only math, avoiding the string allocation entirely?
Approach 2: Full Number Reversal
Intuition
Instead of converting to a string, we can reverse the entire number mathematically. Extract digits from the end one at a time using x % 10, and build the reversed number by multiplying the accumulator by 10 and adding each digit. If the reversed number equals the original, it's a palindrome.
The one thing to watch out for: negative numbers always have the minus sign at the front, which can't appear at the back, so they're never palindromes. Handle that upfront.
The modulo operator % 10 peels off the last digit, and integer division / 10 removes it. By repeatedly doing this, we extract digits from right to left. Building the reversed number by multiplying by 10 each time effectively shifts previous digits left, just like writing digits from left to right. If the original and reversed numbers match, every digit mirrors its counterpart, which is exactly the definition of a palindrome.
Algorithm
- If x is negative, return false immediately.
- Store the original value of x.
- Initialize
reversedto 0. - While x is greater than 0, extract the last digit (
x % 10), append it toreversed(reversed * 10 + digit), and remove the last digit from x (x / 10). - Compare
reversedwith the original value. If equal, it's a palindrome.
Example Walkthrough
Code
- Time Complexity: O(d) where d is the number of digits (equivalently O(log10(x))). We process each digit exactly once.
- Space Complexity: O(1). We only use a fixed number of integer variables regardless of input size.
This works with O(1) space, but we reverse the entire number when we only need half. Reversing the full number also risks integer overflow for values near INT_MAX. What if we only reversed half the digits?
Approach 3: Reverse Half the Number
Intuition
Instead of reversing the whole number, only reverse the second half and compare it with the first half. For 1221, reverse the last two digits to get 12, and the remaining first half is also 12. They match, so it's a palindrome.
The trick is knowing when to stop. We keep extracting digits from the end until the reversed half is greater than or equal to the remaining number. At that point, we've processed exactly half the digits (or just past half for odd-length numbers).
This approach has two advantages over full reversal: it does half the work, and it completely avoids integer overflow since the reversed half never exceeds the original number.
The loop condition x > reversedHalf is the clever part. Each iteration moves one digit from x to reversedHalf. When reversedHalf catches up to (or overtakes) x, we know we've processed exactly half the digits.
For even-length numbers like 1221, after two iterations x = 12 and reversedHalf = 12, and the loop stops because 12 is not greater than 12. A direct comparison works.
For odd-length numbers like 12321, after three iterations x = 12 and reversedHalf = 123. The middle digit (3) got absorbed into reversedHalf, so we divide by 10 to discard it before comparing. This elegantly handles both even and odd cases with a single condition.
Algorithm
- Handle special cases: if x is negative, return false. If x ends in 0 but isn't 0, return false (a number like 10 can't be a palindrome since no number starts with 0).
- Initialize
reversedHalfto 0. - While x is greater than
reversedHalf, extract the last digit of x and append it toreversedHalf. - After the loop, check:
- For even-length numbers:
x == reversedHalf - For odd-length numbers:
x == reversedHalf / 10(the middle digit doesn't need to match anything)
Example Walkthrough
Code
- Time Complexity: O(d/2) which simplifies to O(d) or O(log10(x)). We only process half the digits, though asymptotically it's the same as full reversal.
- Space Complexity: O(1). Only a couple of integer variables, no string allocation, no overflow risk.