9. Palindrome Number

Easy

Question

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:

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

Revert half of the number

For example, input is 1221, if we revert last part of the number 1221 from 21 to 12, and compare with first half.

• When x <= reversed number, we reach the half

• Two cases:

  • "1221" pattern, x == rev.

  • "121" pattern, x == rev / 10, get rid of the middle digit

• Time complexity: O(log_10(n))

• Space complexity: O(1)

Code

def isPalindrome(self, x: int) -> bool:
    # -120 or 10 are not palindrome number
    if x < 0 or (x % 10 == 0 and x != 0):
        return False
    rev = 0 #init reversed number
    while (x > rev):
        rev = rev * 10 + x % 10
        x = x // 10
    return x == rev or x == rev // 10