LeetCode Solutions Blog

Palindrome Number

Number: 9

Difficulty: Easy

Paid? No

Problem Description

Determine whether a given integer is a palindrome. An integer is a palindrome when it reads the same backward as forward, without converting the integer to a string as an extra challenge.

Key Insights

Negative numbers are not palindromic.
A number ending in 0 (except 0 itself) cannot be a palindrome.
Instead of reversing the entire number (risking overflow), reverse only half of the number and compare with the other half.
For numbers with an odd number of digits, the middle digit can be disregarded.

Space and Time Complexity

Time Complexity: O(log10(n)) - Each iteration reduces the number by a factor of 10. Space Complexity: O(1) - Only constant extra space is used.

Solution

The solution checks for obvious non-palindrome cases first (negative numbers and numbers ending with 0 that are not 0). Then, it reverses half of the digits of the number while the original number is larger than the reversed half. Finally, it compares the remaining part of the original number with the reversed half. In the case of an odd number of digits, the middle digit is removed by dividing the reversed half by 10 before the final comparison.

Code Solutions

# Function to check if a number is a palindrome without converting to a string.
def isPalindrome(x):
    # Negative numbers and numbers ending with 0 (but not 0 itself) are not palindromic.
    if x < 0 or (x % 10 == 0 and x != 0):
        return False
    reversed_half = 0
    # Process: Reverse half of the number.
    while x > reversed_half:
        # Add the last digit of x to reversed_half.
        reversed_half = reversed_half * 10 + x % 10
        # Remove the last digit from x.
        x //= 10
    # For numbers with odd digits, reversed_half // 10 removes the middle digit.
    return x == reversed_half or x == reversed_half // 10

# Example usage:
print(isPalindrome(121))   # Output: True
print(isPalindrome(-121))  # Output: False
print(isPalindrome(10))    # Output: False