Palindrome Number easy

Problem Statement

Determine whether an integer is a palindrome. An integer is a palindrome when it reads the same backward as forward. For example, 121 is a palindrome, while 123 is not.

Example 1

Input: x = 121 Output: true

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.

Steps

1. Handle Negative Numbers: Negative numbers are never palindromes because of the minus sign. Return False immediately if the input x is negative.

2. Reverse the Number: Reverse the digits of the input number. We can do this efficiently using integer division and modulo operations.

3. Compare Original and Reversed: Compare the original number x with its reversed version. If they are equal, it's a palindrome; otherwise, it's not.

Explanation

The core idea is to efficiently reverse the integer and then compare it to the original. We avoid converting the number to a string because string manipulation can be less efficient for large integers. The integer division (//) and modulo operator (%) allow us to extract and manipulate individual digits without string conversions.

Code

def isPalindrome(x: int) -> bool:
    """
    Determines if an integer is a palindrome.

    Args:
        x: The integer to check.

    Returns:
        True if x is a palindrome, False otherwise.
    """
    if x < 0:
        return False

    original_number = x
    reversed_number = 0

    while x > 0:
        # Extract the last digit
        last_digit = x % 10
        # Build the reversed number
        reversed_number = reversed_number * 10 + last_digit
        # Remove the last digit from the original number
        x //= 10

    return original_number == reversed_number

Complexity

• Time Complexity: O(log10(n)), where n is the input integer. The number of iterations in the while loop is proportional to the number of digits in the integer, which is logarithmic in the value of n.

• Space Complexity: O(1). The algorithm uses a constant amount of extra space, regardless of the input size. We only store a few integer variables.