9.Palindrome_Number_(Easy).md

9. Palindrome Number (Easy)

Date and Time: Jul 3, 2024, 17:23 (EST)

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

Question:

Given an integer x, return true if x is a palindrome, and false otherwise.

Example 1:

Input: x = 121

Output: true

Explanation: 121 reads as 121 from left to right and from right to left.

Example 2:

Input: x = -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: x = 10

Output: false

Explanation: Reads 01 from right to left. Therefore it is not a palindrome.

Edge case:

Input: x = 1221

Output: true

KeyPoints:

The naive solution to convert int to str is insufficient when x is large. So, there is a efficient way to solve this problem by dividing x into half and only comparing the last half of the x with the front half of x.

The base cases is 1. when x is negative number, we should return False. 2. when x != 0 but the last digit of x is zero, we should also return False, because the palindrome of 10 is 010, which is not possible to have.

Then, we use x % 10 to get the last digit of x and update half by half * 10 + x % 10. Finally, we stop the while loop when x <= half, then we return to compare if x == half (when x is even) or x == (half // 10) (when x is odd).

Optimized Solution:

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

Time Complexity: $O(n)$
Space Complexity: $O(n)$

Naive Solution:

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