Determine whether an integer is a palindrome. An integer is a palindrome when it reads the same backward as forward.
Example 1:
Input: 121
Output: true
Example 2:
Input: -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: 10
Output: false
Explanation: Reads 01 from right to left. Therefore it is not a palindrome.
Follow up:
Could you solve it without converting the integer to a string?
My Solution:
So from what I understand I need a way to determine that one integer reversed is the same as the original integer.
First thing first: check that the number is bigger then 0, and that it is not one digit long or it won’t be considered a palindrome.
An easy solution would be to copy the original number to a temp number and just reverse it by using modulo 10 add the reminder to a summed variable and multiply this sum by 10 before adding the reminder then dividing the temp number by 10 and repeating. Finally compare the summed variable to the original number. If they are the same the integer is a palindrome.
This would be a good approach if we could vouch for the Max integer case, otherwise we would get a type int overflow.
If we can not vouch this then we will need to try a harder approach:
We need to think what are the ways we can reverse the number without using all it’s figures and thus avoiding edge cases such as MAX INT.
So another approach can be splitting it to two and checking if one half is the same as the other reversed half.
But how could we know where the middle of the number is?
1. We can check the length and if it is odd, divide it by 2 and set a mid variable and loop with modulo 10 and divide 10 and sum with multiply 10 like before until the mid count loop and then compare the reversed to the remaining number, if the length is even we can do the same and continue one more loop without summing it but just dividing by 10.
2. We can assume that at until mid point the reversed number should be less then the temp number at mid point the sum should equal and afterwards reversed number should be bigger then temp.
To conclude here is the code for the latter without the extra count variable in cpp:
class Solution {
public:
bool isPalindrome(int x) {
if(x<=0 || (x / 10==0)) return false;
int sum=0;
while (x>sum) {
sum = sum *10 + x%10;
x= x/10;
}
return (x==sum || x == sum/10);
}
};
Complexity Analysis
- Time complexity : we divide the input by 10 every iteration so the time complexity is O(log10(n))
- Space complexity : O(1) for the additional sum variable.