Prompt
Given an integer x, return true if x is a , and false otherwise.
Solve it without converting the integer to a string, and for that matter, no data structures.
Constraints:
-231 <= x <= 231 - 1
Examples
- 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.
Solution
In C++
bool isPalindrome(int x) {
if (x < 0) return false;
unsigned int reverse_accumulator = 0;
int x_copy = x;
while (x_copy > 0) {
reverse_accumulator =
10 * reverse_accumulator
+ x_copy % 10;
x_copy /= 10;
}
return reverse_accumulator == x;
}Explanation
The idea is we construct the reverse of the input, and then check if the reverse equals the original input. If the input is negative it will never be a palindrome. Create an accumulator variable for the reverse and repeatedly shift by one in decimalland, and add the next tail digit of x, which we get from its modulus by 10, and then dividing it by 10 to ready up the next modulus.
Big O Analysis
Time Complexity
The time complexity is where is the number of digits of .
Auxiliary Space Complexity
The space complexity is because the space usage is independent from the input.