[LeetCode] 9. Palindrome Number

Problem https://leetcode.com/problems/palindrome-number/

Simulate the process to check if the first and last digit are the same.

Recursive solution:

Time Complexity : O (log(x))
Space Complexity: O (1)

class Solution(object):
    def isPalindrome(self, x):
        """
        :type x: int
        :rtype: bool
        """
        if x < 0:
            return False

        def helper(x, radix):
            if radix == 0 or x == 0:
                return True

            firstDigit = x // (10 ** radix)
            lastDigit = x % 10

            if firstDigit != lastDigit:
                return False

            return helper((x - firstDigit * (10 ** radix) - lastDigit) // 10, radix - 2)

        radix = 0
        while 10 ** (radix + 1) <= x:
            radix += 1

        return helper(x, radix)

Iterative solution:

Time Complexity : O(log(x))
Space Complexity: O(1)

class Solution(object):
    def isPalindrome(self, x):
        """
        :type x: int
        :rtype: bool
        """

        if x < 0:
            return False

        left = 0
        while 10 ** (left+1) <= x:
            left += 1

        right = 0

        leftx = x
        rightx = x
        while left >= right:
            l = leftx // (10 ** left)
            r = rightx % 10

            if l != r:
                return False

            rightx = rightx // 10
            right += 1

            leftx = leftx - l * (10 ** left)
            left -= 1

            if rightx != 0 and leftx == 0:
                return False

            if rightx == 0 and leftx != 0:
                return False

        return True