Palindrome Number
EasyGiven an integer x, return true if x is a palindrome, and false otherwise. Solve it without converting the integer to a string.
Example
Example 1
Input: x = 121
Output: true
Explanation: 121 reads as 121 from left to right and from right to left.
Example 2
Input: x = -121
Output: false
Explanation: From left to right, it reads -121. From right to left, it becomes 121-. Therefore it is not a palindrome.
Example 3
Input: x = 10
Output: false
Explanation: Reads 01 from right to left. Therefore it is not a palindrome.
Example 4
Input: x = 1221
Output: true
Explanation: Even-length palindrome. We reverse half (21 → 12) and compare with remaining half (12).
Example 5
Input: x = 0
Output: true
Explanation: 0 is a palindrome.
The Intuition
Think about a palindrome. 121. 12321. It's a mirror.
If you stand at the center and look left and right, you see the same thing. But there is a catch. In LeetCode land, the "easy" way is to turn the number into a string. "121". Reverse it. Compare it. Don't do that.
In a high-performance system, converting an integer to a string is "expensive." It allocates memory on the heap. It creates a character array. It involves garbage collection.
To solve this like a Senior Engineer, we stay in the realm of pure math. We need to "flip" the number without ever leaving the CPU's register.
The Logic Breakdown
How do you reverse a number mathematically? You "peel" the digits off from right to left.
-
The Negative Trap:
If a number is negative, like
-121, it reads as121-from the back. Instant "False." Also, if a number ends in 0 (and isn't 0 itself), it can't be a palindrome. Because no number starts with 0. -
The Peeling Process:
To get the last digit of
123:123 % 10 = 3To remove the last digit:
123 / 10 = 12 -
The Rebuilding Process:
To build the reverse:
reversed = (reversed * 10) + popped_digit -
The "Half-Way" Optimization:
We don't actually need to reverse the whole number. If we reverse half of it, it should match the other half. For
1221, if we reverse the last two digits to get12, and the remaining front is12, they match. This prevents integer overflow (a common bug when reversing large numbers).
Idea Map
Check edge cases: x < 0 or (x % 10 == 0 && x != 0) → return false
Initialize revertedNumber = 0
Loop while x > revertedNumber
1. lastDigit = x % 10
2. revertedNumber = revertedNumber * 10 + lastDigit
3. x /= 10
Return x == revertedNumber || x == revertedNumber / 10
Code (Java)
class Solution {
Defines the Solution class as expected by the LeetCode environment.
public boolean isPalindrome(int x) {
Method signature: takes an integer and returns true if it's a palindrome.
// STEP 1: Handle the "Obvious" False cases.
Comment explaining the edge case handling below.
// If x is negative, the '-' sign makes it non-palindromic.
Negative numbers can't be palindromes due to the minus sign.
// If x ends in 0, the first digit must be 0 (which only happens if x is 0).
Numbers ending in 0 (except 0 itself) can't be palindromes.
if (x < 0 || (x % 10 == 0 && x != 0)) {
Check for negative numbers or numbers ending in 0 (excluding 0).
return false;
Return false immediately for these edge cases.
}
End of edge case check.
int revertedNumber = 0;
Initialize the variable to store the reversed half of the number.
// STEP 2: The Math Loop.
Comment explaining the reversal strategy.
// We only want to process HALF of the number to avoid overflow
Processing only half prevents integer overflow issues.
// and save CPU cycles.
Fewer iterations means better performance.
// When 'x' becomes less than or equal to 'revertedNumber',
The loop condition ensures we stop at the middle of the number.
// we've reached the middle.
When x becomes smaller or equal, we've processed half the digits.
while (x > revertedNumber) {
Loop while the remaining original is greater than the reversed part.
// Extract the last digit
Comment for the pop operation.
int pop = x % 10;
Modulo 10 gives us the rightmost digit (e.g., 123 % 10 = 3).
// Push it onto the reverted number
Comment for the push operation.
// (Shifting existing digits left by multiplying by 10)
Multiply by 10 shifts digits left, making room for new digit.
revertedNumber = (revertedNumber * 10) + pop;
Build the reversed number digit by digit.
// Chop the last digit off 'x'
Comment for the chop operation.
x /= 10;
Integer division by 10 removes the last digit (e.g., 123 / 10 = 12).
}
End of the while loop.
// STEP 3: The Result.
Comment explaining the final comparison.
// For even-length numbers (1221): x will be 12, revertedNumber will be 12.
Even-length palindromes: both halves are equal.
// For odd-length numbers (12321): x will be 12, revertedNumber will be 123.
Odd-length palindromes: middle digit is in revertedNumber.
// We divide revertedNumber by 10 to get rid of that middle digit '3'.
For odd-length, we ignore the middle digit by dividing by 10.
return x == revertedNumber || x == revertedNumber / 10;
Check both even-length (direct match) and odd-length (ignore middle) cases.
}
End of method.
}
End of class.
Complexity Analysis
Time Complexity: O(log₁₀ n)
We are dividing the input by 10 in every iteration. The number of iterations is equal to the number of digits in the integer. For a number n, it has log₁₀ n digits.
Space Complexity: O(1)
We are not using any arrays, strings, or recursive stacks. We only store a few primitive integers. This is the "Gold Standard" for memory efficiency.
Related Problems
Learn More
To truly understand why we avoid strings, we need to look at how the JVM handles memory allocation. Converting an integer to a string allocates memory on the heap, creates a character array, and involves garbage collection — all expensive operations.
// String approach (avoid this)
String s = String.valueOf(x); // Heap allocation!
// Math approach (preferred)
int lastDigit = x % 10; // CPU register onlyDisclaimer: This problem is for educational purposes. We encourage you to try solving the 'Palindrome Number' question on LeetCode.