Leetcode – Palindrome Number

Spread the love

In the realm of computer science and algorithmic problem solving, palindromes are an interesting concept. A palindrome is a number or a text that reads the same backwards as forwards. This article aims to discuss the Palindrome Number problem on LeetCode, a popular online platform for preparing for coding interviews. We will explore the problem statement, conceptualize the algorithm, and then dive into different Python-based solutions.

Problem Statement

LeetCode Problem #9: Palindrome Number

Determine whether an integer is a palindrome. An integer is a palindrome when it reads the same backward as forward.

Example

Input: x = 121
Output: true

The problem is quite straightforward: we need to determine if a given integer is a palindrome.

Approach 1: Converting Integer to String

The simplest and most intuitive way to solve this problem is to convert the number into a string and check if the string is a palindrome. Here is a simple Python function that does that:

def isPalindrome(x: int) -> bool:
    str_x = str(x)
    return str_x == str_x[::-1]

This solution leverages Python’s ability to reverse a string using slicing (str_x[::-1]). The time complexity of this solution is O(n), where n is the number of digits in the number, because we need to check each digit.

However, it’s worth noting that this solution might be considered cheating because it doesn’t operate on the number as a number but rather converts it to a string. Additionally, in some programming languages, converting an integer to a string can be costly in terms of time and space complexity.

Let’s now look at a solution that doesn’t involve converting the integer to a string.

Approach 2: Reversing Half of the Number

An alternative approach involves reversing the second half of the number and then comparing it with the first half. If the two halves are the same, the number is a palindrome. This approach doesn’t require converting the number to a string and has a time complexity of O(log(n)), where n is the value of the input number, because we’re only processing half of the digits.

Here’s the Python code that implements this approach:

def isPalindrome(x: int) -> bool:
    # When x < 0, x is not a palindrome.
    # Also if the last digit of the number is 0, in order to be a palindrome,
    # the first digit of the number also needs to be 0.
    # Only 0 satisfy this property.
    if x < 0 or (x % 10 == 0 and x != 0):
        return False

    reversed_number = 0
    while x > reversed_number:
        reversed_number = reversed_number * 10 + x % 10
        x //= 10

    # When the length is an odd number, we can get rid of the middle digit by reversedNumber/10
    # For example when the input is 12321, at the end of the while loop we get x = 12, reversed_number = 123,
    # since the middle digit doesn't matter in palindrome(it will always equal to itself), we can simply get rid of it.
    return x == reversed_number or x == reversed_number // 10

This solution works by repeatedly “popping” the last digit off of x and “pushing” it onto the reversed_number. We stop when x is less than or equal to reversed_number because we’ve processed half of the digits in x.

Conclusion

The Palindrome Number problem provides an opportunity to explore and understand the concept of palindromes in the realm of integers. It shows how a seemingly complex problem can be broken down into manageable parts that can be solved using simple arithmetic operations.

The Python solutions provided here demonstrate different ways to approach the problem. The first solution, which involves converting the integer to a string, is simple and easy to understand but can be costly in terms of time and space complexity. The second solution, which involves reversing half of the number, is more efficient and works within the constraints of the problem (i.e., not converting the integer to a string).

Leave a Reply