Leetcode: Palindrome Number

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

Understand the problem:
The problem asks for determining if an integer is a palindrome. In addition, it requires the in-place results. There are several points to consider:

• For an positive number, e.g. 141, return true;
• For an negative number, e.g. -141, return false, as required by the OJ.
• For integer with single digit, return true

Naive Solution:

One naive solution is to first reverse the integer, and check if they are the same. If works, but at the cost of reversing the integer. Also you need to handle the overflow problem of the reversed integer.

A better Solution:

If an integer is a palindrome, it must be mirrored at the center pointer. So we can start from the beginning and end of the integer, parse the digit, and compare them. We have already know how to parse an integer from the end. But how to do it in forward order? For e.g., 123,

we can get 1 by 123 / 100 = 1, then 123 - 1 * 100  =23

23 / 10 = 2, then 23 - 2 * 10 = 3

3/ 1 = 3, 3 - 3 * 1 = 0

So we must first get the length of the number. In addition, we also need to mark down the current position of the pointer i and j. 

Code (Java):

public class Solution {
    public boolean isPalindrome(int x) {
        if (x < 0) return false;

        // get length of the integer
        int len = 0;
        int temp = x;
        while (temp > 0) {
            len++;
            temp /= 10;
        }
        
        int i = 0;
        int j = len - 1;
        int xLeft = x;
        int xRight = x;
        int n = len;
        while (i < j) {
            // get digit from left
            int lDigit = (int)(xLeft / Math.pow(10, n - 1));
            xLeft -= lDigit * Math.pow(10, n - 1);
            n--;
            
            // get digit from right
            int rDigit = xRight % 10;
            xRight /= 10;
            
            if (lDigit != rDigit) return false;
            
            i++;
            j--;
        }
        return true;
    }
}

Discussion:
We can see that the solution above has time complexity O(n) and space complexity O(1).