Palindrome Number
Asked at Google, Amazon, Microsoft
Problem
Determine whether an integer is a palindrome without converting it to a string. The optimal approach reverses only half of the number and compares, avoiding O(n) space for string conversion.
Asked At
| Company | Difficulty | |
|---|---|---|
| Easy | View all Google questions → | |
| Amazon | Easy | View all Amazon questions → |
| Microsoft | Easy | View all Microsoft questions → |
How to Think About It
Brute force: convert to string, check if it reads the same forwards and backwards. O(n) time and space. The interviewer will ask you to avoid string conversion.
Key insight: reverse the second half of the number and compare it to the first half. If they match, the number is a palindrome.
Why reverse half: for 1221, reversing the last two digits gives 12. Compare 12 == 12 (first half). For 12321, reversing gives 123. Compare 12 == 123 // 10 = 12.
How to know when half is reversed: when reversed >= original, you have processed at least half the digits. For even-length numbers, reversed == original. For odd-length, reversed // 10 == original (ignore the middle digit).
Visual walkthrough for 1221:
original=1221, reversed=0
Step 1: reversed=1, original=122
Step 2: reversed=12, original=12
reversed >= original → stop. Check: 12 == 12 → palindrome.
Visual walkthrough for 12321:
original=12321, reversed=0
Step 1: reversed=1, original=1232
Step 2: reversed=12, original=123
Step 3: reversed=123, original=12
reversed >= original → stop. Check: 12 == 123 // 10 = 12 → palindrome.
Edge cases: negative numbers (not palindromes), numbers ending in 0 (not palindromes unless 0 itself), single digit (always palindrome).
Optimal Approach
Step 1: If x < 0 or (x % 10 == 0 and x != 0), return false.
Step 2: Initialize reversed = 0.
Step 3: While x > reversed:
reversed = reversed * 10 + x % 10
x //= 10
Step 4: Return x == reversed or x == reversed // 10.
The second condition in step 4 handles odd-length numbers where the middle digit is in reversed but not in x.
Time: O(log n) — we process half the digits. Space: O(1) — no extra data structures.
What Trips People Up in Real Interviews
Converting to a string. The problem asks for a solution without string conversion. Use the half-reversal approach.
Forgetting to handle negative numbers. All negative numbers are not palindromes because of the minus sign.
Not handling numbers ending in 0. A number like 10 is not a palindrome. Check x % 10 == 0 and x != 0 at the start.
Comparing the full reversed number to the original. For odd-length numbers, the middle digit ends up in reversed but not in x. Compare x == reversed // 10 to ignore it.
Overflow when reversing. Since we only reverse half the digits, the reversed value stays within int range. No overflow risk.
Solution Code
def isPalindrome(x):
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 // 10Frequently Asked Questions
What is the Palindrome Number problem?
Determine whether an integer is a palindrome without converting it to a string. The optimal approach reverses only half of the number and compares, avoiding `O(n)` space for string conversion.
How do you solve Palindrome Number?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Palindrome Number?
Palindrome Number is asked at Google, Amazon, Microsoft. It is a easy difficulty problem.
What are common mistakes on Palindrome Number?
- Converting to a string. The problem asks for a solution without string conversion. Use the half-reversal approach.
- Forgetting to handle negative numbers. All negative numbers are not palindromes because of the minus sign.
- Not handling numbers ending in 0. A number like 10 is not a palindrome. Check `x % 10 == 0 and x != 0` at the start.
- Comparing the full reversed number to the original. For odd-length numbers, the middle digit ends up in `reversed` but not in `x`. Compare `x == reversed // 10` to ignore it.
- Overflow when reversing. Since we only reverse half the digits, the reversed value stays within `int` range. No overflow risk.