LeetCode/009 Palindrome Number.py at master · zgdgod/LeetCode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
"""
Determine whether an integer is a palindrome. Do this without extra space.
"""
__author__ = 'Danyang'


class Solution:
    def isPalindrome(self, x):
        """
        Algorithm: int, compare lsb and msb
        No extra space
        If you are thinking of converting the integer to string, note the restriction of using extra space.

        :param x: int
        :return: boolean
        """
        if x < 0:
            return False

        # find order of magnitude
        div = 1
        while x/div >= 10:
            div *= 10  # without touch x

        while x > 0:
            msb = x/div
            lsb = x%10

            if msb != lsb:
                return False

            # shrink
            x %= div
            x /= 10

            div /= 100

        return True


if __name__ == "__main__":
    Solution().isPalindrome(2147483647)