9. Palindrome Number

Intuition

A palindrome number reads the same forward and backward. For example, 121 is a palindrome because it reads as 121 from left to right and 121 from right to left. However, -121 is not a palindrome because it reads as -121 from left to right but 121- from right to left.

The key insight is that we don’t need to reverse the entire number. We can stop when we’ve processed half of the digits. This optimization reduces both time complexity and avoids potential integer overflow issues.

Approach

The solution uses an efficient approach that only reverses half of the number:

1. If the number is negative, it’s not a palindrome. If the number ends with 0 (except 0 itself), it’s not a palindrome.

2. Instead of reversing the entire number, we only reverse half of it:

   • Extract digits from the right side of the original number
   • Build the reversed number from these digits
   • Stop when the original number becomes less than or equal to the reversed number

3. For even-length numbers, compare x == reversed. For odd-length numbers, compare x == reversed // 10 (to remove the middle digit from the reversed half).

This approach ensures we only process half the digits, making it more efficient and avoiding potential overflow issues.

Solution Code

class Solution:
    def isPalindrome(self, x: int) -> bool:
        # Negative numbers are not palindromes
        # Numbers ending with 0 (except 0 itself) are not palindromes
        if x < 0 or (x % 10 == 0 and x != 0):
            return False
        
        reversed_half = 0
        
        # Reverse only half of the number
        while x > reversed_half:
            # Extract the last digit and add it to reversed_half
            reversed_half = reversed_half * 10 + x % 10
            # Remove the last digit from x
            x //= 10
        
        # For even-length numbers: x == reversed_half
        # For odd-length numbers: x == reversed_half // 10
        # (the middle digit doesn't need to be checked)
        return x == reversed_half or x == reversed_half // 10

Time & Space Complexity

• Time Complexity: O(log(n))

  • We only process half of the digits in the number
  • The number of digits in an integer n is log(n), so we process log(n)/2 digits
  • Therefore, the time complexity is O(log(n))

• Space Complexity: O(1)

  • We only use a constant amount of extra space for variables
  • No additional data structures are needed
  • Therefore, the space complexity is O(1)