tags: `leetcode`

9. Palindrome Number

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?

Revers a linked list, recursive
https://hackmd.io/@y56/H1cQj8kIH

strategy #0

convert to string
compare from head and tail

try #0 success










class Solution:
    def isPalindrome(self, x: int) -> bool:
        a = str(x)
        output = True  # default flag as True
        i = 0
        while output is True and i <= (len(a) // 2 - 1):
            if a[i] != a[-1 - i]:
                output = False
            i = i + 1
        return output

try #1 from others

short



class Solution:
    def isPalindrome(self, x: int) -> bool:
        return str(x) == str(x)[::-1]

try #2 from others

a pointer-flavor method

It doesn't have to deal with length/2
while (start < end) {array(start++) vs array(end--)}









public boolean isPalindrome(int x) {
    String str = String.valueOf(x);
    int start = 0;
    int end = str.length() - 1;
    while(start < end){
        if(str.charAt(start++) != str.charAt(end--)) return false;
    }
    return true;
}

strategy #1

not to use string
See solution: https://leetcode.com/problems/palindrome-number/solution/
- don't need to handle overflow
- use math

Now let's think about how to revert the last half of the number. For number 1221, if we do 1221 % 10, we get the last digit 1, to get the second to the last digit, we need to remove the last digit from 1221, we could do so by dividing it by 10, 1221 / 10 = 122. Then we can get the last digit again by doing a modulus by 10, 122 % 10 = 2, and if we multiply the last digit by 10 and add the second last digit, 1 * 10 + 2 = 12, it gives us the reverted number we want. Continuing this process would give us the reverted number with more digits.

Now the question is, how do we know that we've reached the half of the number?

Since we divided the number by 10, and multiplied the reversed number by 10, when the original number is less than the reversed number, it means we've processed half of the number digits.

try #0 fail













class Solution:
    def isPalindrome(self, x: int) -> bool:
        if x < 0:
            return False
        y = 0 # those digits taken from the tail of x, in reversed order
        while x > y:
            y = y * 10 + x % 10
            x //= 10
        if x == y:
            return True
        if x == y // 10:
            return True
        return False

Input
10
Output
true
Expected
false

It works for 121 but not for 10.
I realize that 10, 100 and 1000 are special cases.
(Also, 12210000000000)
The y part will not grow when cut digits from x and paste them to y.

try #1 fail













class Solution:
    def isPalindrome(self, x: int) -> bool:
        if x < 0 or x % 10 == 0:
            return False
        y = 0 # those digits taken from the tail of x, in reversed order
        while x > y:
            y = y * 10 + x % 10
            x //= 10
        if x == y:
            return True
        if x == y // 10:
            return True
        return False

Input
0
Output
false
Expected
true

I use x % 10 == 0 but 0 shall pass.

try #2 success

















class Solution:
    def isPalindrome(self, x: int) -> bool:
        if x < 0:
            return False
        if x < 10:
            return True
        if x % 10 == 0:
            return False
        y = 0 # those digits taken from the tail of x, in reversed order
        while x > y:
            y = y * 10 + x % 10
            x //= 10
        if x == y:
            return True
        if x == y // 10:
            return True
        return False

strategy #2 from others

no string
don't care overflow









class Solution:
    def isPalindrome(self, x: int) -> bool:
        if x < 0:
            return False
        p, res = x, 0
        while p:
            res = res * 10 + p % 10
            p //= 10
        return res == x

strategy #3 from others

no string
take care of overflow















public boolean isPalindrome(int x) {
    
    if (x < 0) return false;

    int p = x; 
    int q = 0; 
    
    while (p >= 10){
        q *=10; 
        q += p%10; 
        p /=10; 
    }
    
    return q == x / 10 && p == x % 10;
}

strategy #4 from others

no string
take care of overflow












class Solution:
    def isPalindrome(self, x):
        if x < 0:
            return False
        b = 1
        while x // b >= 10:
            b *= 10
        while b >= 10:
            if x // b != x % 10:
                return False
            x, b = (x % b) // 10, b // 100
        return True

tags: leetcode