Palindrome Number

Problem

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

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.

Solution

Convert to String: O(n) time and O(n) space

public class Solution {
    public boolean isPalindrome(int x) {
        if (x < 0) return false;
        char[] chars = Integer.toString(x).toCharArray();
        int start = 0, end = chars.length - 1;
        while (start < end) {
            if (chars[start] != chars[end]) return false;
            start++;
            end--;
        }
        return true;
    }
}

Calculate Value: O(lg n) time O(1) space

public class Solution {
    public boolean isPalindrome(int x) {
        if (x < 0) return false;
        int num = x, reversed = 0;
        while (num >= 10) {
            reversed *= 10;
            reversed += num % 10;
            num /= 10;
        }
        return reversed == x / 10;
    }
}

Analysis

The first solution is typical palindrome checking solution using two pointers
However, since this is about integer we came up with the second solution using value
We calculate the reversed number of given x and store it to reversed
To avoid overflow exception, we leave the last digit and while loop becomes while (num >= 10)
Then at the, we just if reversed value of x equal to x / 10