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.
1public class Solution {
2 public bool IsPalindrome(int x) {
3 if (x < 0) return false;
4 string str = x.ToString();
5 int n = str.Length;
6 for (int i = 0; i < n / 2; i++) {
7 if (str[i] != str[n - i - 1]) return false;
8 }
9 return true;
10 }
11}
12The method converts the integer to a string. It then iterates over the string, comparing characters from the start and the end, moving toward the center. If any characters mismatch, it returns false, otherwise true if all match.
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.
1 public 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).
This method handles situations where x is negative or ends with zero, as such numbers cannot be palindromes. It iteratively builds the reversed half by manipulating digits and compares the two halves for equality.