###### 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.
:::info
Follow up:
Coud you solve it without converting the integer to a string?
:::
:::success
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

:::danger
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

:::danger
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