Determine whether an integer is a palindrome. An integer is a palindrome when it reads the same backward as forward.

Example 1:

Input: 121
Output: true

Example 2:

Input: -121
Output: false
Explanation: From left to right, it reads -121. From right to left, it becomes 121-. Therefore it is not a palindrome.

Example 3:

Input: 10
Output: false
Explanation: Reads 01 from right to left. Therefore it is not a palindrome.

Follow up:

Coud you solve it without converting the integer to a string?

[code lang="java"]
class Solution {
    public boolean isPalindrome(int x) {
        
    }
}
[code]

Idea – 1

If a number has a negative sign, it cannot be a palindrome number. Otherwise, we match digits from the two ends. Time complexity is O\left(\log_{10} n\right) and space complexity is O(1). 
[code lang="java"]
class Solution {
    public boolean isPalindrome(int x) {
        if(x < 0)
        {
            return false;
        }
        
        // single digit is palindrome
        if(x < 10)
        {
            return true;
        }
        
        int j = (int)Math.log10(x);
        int i = 0;
        
        while(i < j)
        {
            if(getDigit(x, i++) != getDigit(x, j--))
            {
                return false;
            }
        }
        
        return true;
    }
    
    private int getDigit(int x, int i)
    {
       int msbExponent = (int)Math.log10(x);    
       int msbPower = (int)Math.pow(10, msbExponent);
        
       if(i == msbExponent)
       {
           return x/msbPower;
       }
        
       int MOD = (int)Math.pow(10, i+1);
       int ans = x%MOD;
       int DIV = (int)Math.pow(10, i);
       ans /= DIV;
        
       return ans;
    }
}
[code]

Runtime: 27 ms, faster than 57.69% of Java online submissions for Palindrome Number.Memory Usage: 34.9 MB, less than 80.99% of Java online submissions for Palindrome Number.

Leave a comment