Given an integer x, return true if x is a palindrome, and false otherwise.
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.
Constraints:
-231 <= x <= 231 - 1The Palindrome Number problem asks whether a given integer reads the same forward and backward. A straightforward idea is to convert the number to a string and compare characters from both ends. However, interviewers often expect a math-based approach that avoids extra string storage.
The key idea is to reverse part of the number using arithmetic operations. By repeatedly extracting the last digit using % 10 and building a reversed value with * 10, you can compare digits from both ends. An optimization is to reverse only half of the number instead of the entire value, which avoids overflow risks and reduces unnecessary work.
During iteration, once the reversed half becomes greater than or equal to the remaining half, the comparison can determine whether the number is a palindrome. Special cases such as negative numbers or numbers ending with zero (except zero itself) should be handled early.
This approach works efficiently with O(log n) time complexity and O(1) extra space.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| String Comparison | O(d) | O(d) |
| Reverse Half Using Math | O(log n) | O(1) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
Beware of overflow when you reverse the integer.
In this method, we convert the integer to a string and check if it reads the same forwards and backwards. This approach is straightforward and leverages the built-in string operations.
Time Complexity: O(n), where n is the length of the string representation of the number.
Space Complexity: O(n) for the string conversion.
1def isPalindrome(x: int) -> bool:
2 if x < 0:
3 return False
4 return str(x) == str(x)[::-1]
5After checking if the number is negative, the function converts the number to a string and uses Python slicing to reverse the string. It compares the original and reversed string to check if they are the same.
This approach avoids the use of string conversions by reversing half of the digits of the number and comparing the two halves. This is more memory efficient as it only creates a few integer variables.
Time Complexity: O(log10(n)), where n is the input number because we are dividing the number by 10 in each iteration.
Space Complexity: O(1) because no additional space proportional to input size is used.
1public:
bool isPalindrome(int x) {
if (x < 0 || (x % 10 == 0 && x != 0)) return false;
int reversedHalf = 0;
while (x > reversedHalf) {
reversedHalf = reversedHalf * 10 + x % 10;
x /= 10;
}
return x == reversedHalf || x == reversedHalf / 10;
}
};
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, Palindrome Number is a common easy-level interview question used to test understanding of numbers, digit manipulation, and edge cases. Variations of it frequently appear in interviews at major tech companies.
The optimal approach reverses only half of the integer using mathematical operations. This avoids converting the number to a string and prevents overflow issues. It runs in O(log n) time with constant space.
Negative numbers are never palindromes because of the minus sign. Numbers ending with zero (except zero itself) also cannot be palindromes. Handling these cases early simplifies the solution.
Yes, the problem can be solved using pure math by extracting digits with modulo and building a reversed half of the number. Once half is reversed, you compare it with the remaining digits. This keeps the space complexity at O(1).
The function first deals with negative numbers and numbers ending with zero. It then reverses digits from the end of the number to form half of the reversed number. This leverages integer arithmetic properties to compare the first half with the second half of the number.