Palindrome Number

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

click to show spoilers.

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.

In order to check if a number is a palindrome, we need to keep checking the first and last digit of the number. To get the last digit is trivial, i.e., x % 10, but how to get the first digit?

Thinking about how you will do to trim the last digit from a number? Divide the number by 10, right? So this time, we do it in the reverse way: multiply a number by 10: Start from 1, if x / divisor >= 10, it means we haven't reached the first digit, we need to keep multiply the divisor by 10, until we reach the first the digit. Note I did it this way at first:

int divisor = 1;
        while (divisor < x)
            divisor *= 10;
        divisor /= 10;

The divisor will overflow for large x, so no, this won't work.

The rest part is easy, keep checking the first and last digit and divide the divisor by 100 (each time we trim two digits).

public boolean isPalindrome(int x) {
        if (x < 0)
            return false;
        if (x > 0 && x < 10)
            return true;
        int divisor = 1;
        while (divisor < x)
            divisor *= 10;
        divisor /= 10;
        while (x > 0) {
            int right = x % 10;
            int left = x / divisor;
            if (left != right)
                return false;
            x -= (x / divisor * divisor);
            x /= 10;
            divisor /= 100;
        }
        return true;
    }