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.
1#include <iostream>
2
3bool isPalindrome(int x) {
4 if (x < 0) return false;
5 std::string str = std::to_string(x);
6 int n = str.size();
7 for (int i = 0; i < n / 2; ++i) {
8 if (str[i] != str[n - i - 1]) return false;
9 }
10 return true;
11}
12We check if the number is negative, returning false early if it is. We convert the integer to a string and compare each character from the start and end moving toward the center. If all pairs match, the integer is a palindrome.
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
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 checks if the number is negative or ends with a zero (and is not zero itself), returning false in those cases. It then sequentially takes digits from the end of the number, constructing a reversed half. The loop terminates once reversedHalf equals or exceeds the original half of the number, allowing us to check equality.