LeetCode (Algorithms#9) ‒ Palindrome Number

Problem

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

Solution

First, note that the complexity of the problem should be on the order of the number of digits in the integer. Thus, as long as you only use numeric data types (single instances, not arrays), your code will run in O(1) space. The problem is again similar to that of Reverse Integer, but with some optimizations we can make.

There are a few cases that can be determined to produce an early decision for the function, these are in the first few lines of the code below (note the last line, which decides in O(1) whether a two digit number is a palindrome). Other than these conditions, the main optimization is to only reverse half of the number. We do not actually know the length of the number, so we keep checking for equality between the original and reversed portion of the number until the original becomes shorter than the reversed: x / 10 =< xr.

Time complexity: O(n)
Space complexity: O(n)
Runtime percentile: 89.99%

public boolean isPalindrome(int x) {
    if (x < 0 || (x!=0 && x % 10 == 0)) return false;
    else if (x < 10) return true;
    else if (x < 100) return x % 11 == 0;   
    long xr = 0;
    while (x > 0 && x/10 > xr) {
        xr = xr*10 + x%10;
        x /= 10;
        if (x == (int)xr || x/10 == (int)xr) return true;
        else if (xr > Integer.MAX_VALUE) return false;
    }
    return false;
}