9.Palindrome Number

Posted on | In

Question：

Determine whether an integer is a palindrome . Do this without extra space.

Example：

12321

Some hints：

Could negative integers be palindromes? (ie, -1)

If you are thinking of converting the integer to string, note the restriction of using extra space.

You could also try reversing an integer. However, if you have solved the problem “Reverse Integer”, you know that the reversed integer might overflow. How would you handle such case?

There is a more generic way of solving this problem.

My answer (java)： 

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public boolean isPalindrome(int x) {
        int rev=0;
        int ori=x;
        if (x<0 || (x!=0 && x%10==0)) 
            return false;
        while(x!=0){
            rev=rev*10+x%10;
            x=x/10;
        }
        return ori==rev;
    }
}

Better answer (java)：

1
2
3
4
5
6
7
8
9
public boolean isPalindrome(int x) {
    if (x<0 || (x!=0 && x%10==0)) return false;
    int rev = 0;
    while (x>rev){
    	rev = rev*10 + x%10;
    	x = x/10;
    }
    return (x==rev || x==rev/10);
}

Algorithm：

First of all we should take care of some edge cases. All negative numbers are not palindrome, for example: -123 is not a palindrome since the ‘-‘ does not equal to ‘3’. So we can return false for all negative numbers.

Now let’s think about how to revert the last half of the number. For number 1221, if we do 1221 % 10, we get the last digit 1, to get the second to the last digit, we need to remove the last digit from 1221, we could do so by dividing it by 10, 1221 / 10 = 122. Then we can get the last digit again by doing a modulus by 10, 122 % 10 = 2, and if we multiply the last digit by 10 and add the second last digit, 1 * 10 + 2 = 12, it gives us the reverted number we want. Continuing this process would give us the reverted number with more digits.

Now the question is, how do we know that we’ve reached the half of the number?

Since we divided the number by 10, and multiplied the reversed number by 10, when the original number is less than the reversed number, it means we’ve processed half of the number digits.

My answer (python):

1
2
3
4
5
6
7
8
9
10
11
class Solution(object):
    def isPalindrome(self, x):
        """
        :type x: int
        :rtype: bool
        """
        
        if(str(x)==str(x)[::-1]) and -2147483648 <= x <= 2147483647:
            return True
        else: 
            return False