Palindrome Number

Difficulty: Easy | Acceptance: 59.55% | Paid: No

Topics: Math

• Examples
• Constraints
• String Conversion Approach
• Revert Half Approach
• Recursive Approach

Examples

Input

x = 121

Output

true

Explanation

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

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.

Input

x = 10

Output

false

Explanation

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

Constraints

- -2^31 <= x <= 2^31 - 1

String Conversion Approach

Intuition

The easiest way to check if a number is a palindrome is to convert it to a string and compare it with its reverse.

Steps

• Convert the integer x to a string representation.
• Compare the string with its reversed version.
• If they are equal, then x is a palindrome; otherwise, it is not.

class Solution:
    def isPalindrome(self, x: int) -> bool:
        if x < 0:
            return False
        x_str = str(x)
        return x_str == x_str[::-1]

Complexity

• Time: O(log n), where n is the value of the integer x. This is because converting the integer to a string takes O(log n) time.
• Space: O(log n), where n is the value of the integer x. This is due to the storage of the string representation.

Revert Half Approach

Intuition

Instead of converting the number to a string, we can reverse half of the integer and compare it with the other half. This avoids the extra space needed for string conversion.

Steps

• If x is negative, return false immediately since negative numbers cannot be palindromes.
• If x ends with 0 (and x is not 0), it cannot be a palindrome because numbers don’t have leading zeros.
• Reverse half of the digits of x. This is done by extracting the last digit of x and building the reversed number.
• Stop reversing when the original number x becomes less than or equal to the reversed number.
• If x is equal to the reversed number (for even number of digits) or x is equal to reversed number divided by 10 (for odd number of digits), then it is a palindrome.
• Handle the case where x is 0 separately.

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

Complexity

• Time: O(log n), where n is the value of the integer x. This is because we process half of the digits of x, and the number of digits is proportional to log n.
• Space: O(1). We only use a constant amount of extra space for the reversedHalf variable.

Recursive Approach

Intuition

A palindrome reads the same forward and backward. We can use recursion to check if the first and last digits are the same and then recursively check the remaining substring.

Steps

• Convert the integer x to a string.
• Create a recursive helper function that takes two indices, start and end.
• In the base case, if start index is greater than or equal to end index, return true.
• In the recursive case, compare the characters at start and end indices. If they are not equal, return false.
• If they are equal, make a recursive call with start + 1 and end - 1.
• Return the result of the recursive call.

class Solution:
    def isPalindrome(self, x: int) -> bool:
        if x < 0:
            return False
        x_str = str(x)
        return self.is_palindrome_recursive(x_str, 0, len(x_str) - 1)
    
    def is_palindrome_recursive(self, s: str, start: int, end: int) -> bool:
        if start >= end:
            return True
        
        if s[start] != s[end]:
            return False
        
        return self.is_palindrome_recursive(s, start + 1, end - 1)

Complexity

• Time: O(log n), where n is the value of the integer x. In the worst case, we make a recursive call for each character in the string representation of x.
• Space: O(log n), where n is the value of the integer x. This is due to the recursive call stack depth, which goes up to the number of digits in x.