0009. Palindrome Number

Easy | Math | 40 ms (93.69%), 13.2 MB (90.79%)

❓ Problem Statement

Source: LeetCode - Palindrome Number GitHub: Solution / Performance

Given an integer x, return true if x is palindrome integer.

An integer is a palindrome when it reads the same backward as forward. For example, 121 is palindrome while 123 is not.

✍🏻 Constraints & Example

Constraints:

• -2^31 <= x <= 2^31 - 1

Input: x = 121
Output: true

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

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

Input: x = -101
Output: false

💡 Ideas

We could find the answer by reverting half of the number. For odd length, the middle digit could be ignored by // 10.

12321, rev = 123, x = 12 (rev // 10 == x)
9119,  rev = 91,  x = 91 (rev == x)
4321,  rev = 123, x = 4
1234,  rev = 43,  x = 12

🤖 Python3

class Solution:
    def isPalindrome(self, x: int) -> bool:
        # (base case)
        if x <  0 or (x != 0 and x % 10 == 0): return False
        if x < 10: return True
        
        # ==================================================
        #  Math                                            =
        # ==================================================
        # time  : O(log(n))
        # space : O(1)
        
        rev = 0
        
        # loop until reversed integer > divided integer
        while x > rev:
            pop = x % 10
            x //= 10
            
            rev = rev*10 + pop
        
        # for odd length, middle digit could be ignored by // 10
        if x == rev or x == rev // 10: return True
        else: return False

🤖 Java

class Solution {
    /**
     * @time  : O(log(n))
     * @space : O(1)
     */
     
    public boolean isPalindrome(int x) {
        if(x < 0 || (x != 0 && x % 10 == 0)) return false;
        if(x < 10) return true;
        
        int rev = 0;
        
        while(x > rev) {
            rev = rev*10 + x % 10;;
            x /= 10;
        }
        
        if(x == rev || x == rev/10) return true;
        else return false;
    }
}