DSA problem
Palindrome Number
Given an integer x, return true if x is a palindrome and false otherwise. An integer is a palindrome when it reads the same forward and backward in base 10. Negative numbers are never palindromes because the minus sign is not mirrored on the right.
The obvious solution converts the number to a string and checks whether the string equals its reverse. That works in O(d) time where d is the digit count, but the problem follow-up asks us to avoid the string conversion — a useful constraint in embedded or interview settings.
A second approach reverses the entire number arithmetically (rev = rev * 10 + x % 10), but on a 32-bit machine the reversed integer can overflow if the original is close to INT_MAX. We would have to use a 64-bit accumulator just to be safe.
The cleanest digit-based method reverses only the lower half of the number and compares it to the upper half. Loop while x > rev, updating rev = rev * 10 + x % 10 and x //= 10. When the loop ends, either x == rev (even-length palindrome, all digits matched) or x == rev // 10 (odd-length palindrome, where rev includes the middle digit but x does not). Negative numbers, and any positive number ending in zero (other than zero itself), can be rejected up front. The algorithm runs in O(d) time and O(1) space without ever using strings.
Examples
x = 121truex = -121falsex = 10falseConstraints
- -2^31 <= x <= 2^31 - 1
- Follow-up: avoid converting the integer to a string.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.