Solution Explanation: Palindrome Number

This problem asks to determine if an integer is a palindrome. A palindrome reads the same forwards and backward. The efficient approach avoids converting the integer to a string.

Algorithm (Reverse Half):

1. Handle Special Cases:

   • Negative numbers are not palindromes (return false).
   • Numbers ending in 0 (except 0 itself) are not palindromes (return false). This is because a palindrome must have the same first and last digits.

2. Reverse the Second Half: The core idea is to reverse only the right half of the number and compare it to the left half. We don't need to reverse the entire number, which improves efficiency. This is done iteratively:

   • Initialize y to 0 (to store the reversed number).
   • In a loop, continue as long as y is less than x.
   • In each iteration:
     • Extract the last digit of x using the modulo operator (x % 10).
     • Add this digit to the end of y by multiplying y by 10 and adding the last digit (y = y * 10 + x % 10).
     • Remove the last digit from x by integer division (x //= 10 or x /= 10).

3. Compare: After the loop, there are two possibilities:

   • x and y are equal (the number was a palindrome with an odd number of digits).
   • x is equal to y / 10 (the number was a palindrome with an even number of digits).

Time Complexity: O(log₁₀(n))

The loop runs approximately half the number of digits in the input integer n. The number of digits is proportional to log₁₀(n). Therefore, the time complexity is logarithmic with respect to the input number.

Space Complexity: O(1)

The algorithm uses a constant amount of extra space to store variables like x, y.

Code Examples (Python):

class Solution:
    def isPalindrome(self, x: int) -> bool:
        if x < 0 or (x and x % 10 == 0): #Handle Negative and trailing zero cases
            return False
        y = 0
        while y < x:
            y = y * 10 + x % 10
            x //= 10
        return x == y or x == y // 10 #Check for both even and odd digit palindrome
 

Other language implementations follow the same logic, varying only in syntax. The core steps of handling special cases, reversing half the number, and comparing remain consistent across all languages.