Palindrome Number Leetcode Problem 9 [Python Solution]

Welcome to another exciting coding adventure!

Today, we're going to tackle the Palindrome Number problem, which is Problem 9 on LeetCode.

In this problem, we're given an integer x, and our mission is to determine whether it's a palindrome or not.

But here's the twist: we need to do it without converting the integer to a string.

I'll walk you through a step-by-step Python solution that will make this challenge a piece of cake.

If you want to follow along with the problem description, here's the link.

Problem Overview

Example 1:

Let's start with a simple example to illustrate the concept.

Consider x = 121.

Our task is to check whether this number is a palindrome or not.

A palindrome is a number that reads the same forward and backward.

In this case, 121 is indeed a palindrome because it reads the same way from left to right and right to left.

Example 2:

Now, let's take a look at a more complex scenario.

Suppose x = -121.

In this case, it's not a palindrome.

Why?

Well, when we read it from left to right, it's -121. However, when we read it backward, it becomes 121-.

So, the negative sign at the end makes it non-palindromic.

Example 3:

Finally, let's examine another non-palindromic case: x = 10.

When we read it from right to left, it becomes 01. Since 01 is not the same as 10, it's clear that 10 is not a palindrome.

Understanding the Constraints

Before we dive into the solution, let's consider the constraints of the problem.

The integer x can range from -2^31 to 2^31 – 1. This information is crucial because it will help us design an efficient solution that works for a wide range of inputs.

Palindrome Number LeetCode Problem Solution

Bruteforce Approach

Now that we've grasped the problem, let's start with the brute-force approach.

While this may not be the most efficient solution, it's a good starting point to understand the problem.

def isPalindrome(x: int) -> bool:
    if x < 0:
        return False

    # Convert the integer to a string for easy comparison.

x_str = str(x)
    return x_str == x_str[::-1]

In this approach, we first check if the number is negative.

If it is, we return False since negative numbers are never palindromic.

Then, we convert the integer to a string and check if it's equal to its reverse.

If they are the same, we return True, indicating that the number is a palindrome.

Otherwise, we return False.

While this approach works, it doesn't meet the problem's requirement of not converting the integer to a string.

So, let's move on to a more efficient solution that adheres to the constraints.

An Efficient Approach with Mathematical Operations

In the efficient approach, we won't convert the integer to a string.

Instead, we'll use mathematical operations to determine if it's a palindrome.

Here's the Python code:

View on GitHub ➹

def isPalindrome(x: int) -&gt; bool:
    if x &lt; 0:
        return False

    div = 1
    while x &gt;= 10 * div:
        div *= 10

    while x:
        right = x % 10
        left = x // div

        if left != right:
            return False

        x = (x % div) // 10
        div //= 100

    return True

Let's break down the code and understand how it works.

First, we check if the input integer x is negative.

If it is, we return False since negative numbers can't be palindromic.

Next, we initialize a variable div to 1. This variable will help us extract the left and right digits for comparison.
We enter a while loop, where we repeatedly update div until it's greater than or equal to ten times the original number x.

This loop's purpose is to determine the scale of div.

For example, if x is 121, we want div to be 100 because it's the most significant digit in this case.

Now, we enter another while loop, which runs until x becomes 0. Inside this loop, we perform the following steps:
- Calculate the right digit by taking x % 10.

This operation extracts the last digit from x.
– Calculate the left digit by taking x // div.

The // operator is used for integer division.

This step gives us the most significant digit.
– Compare the left and right digits.

If they are not equal, we immediately return False because the number can't be a palindrome.

After the comparison, we need to update x and div to continue checking the remaining digits.

We do this by first chopping off the left and right digits from x using (x % div) // 10.

This operation effectively removes the last and first digits, preparing the number for the next comparison.

Additionally, we update div by dividing it by 100, as we have now processed two digits.

If the loop completes without any unequal left and right digit comparisons, we return True, indicating that the number is a palindrome.

This efficient approach solves the problem without converting the integer to a string, making it both elegant and performant.

Time and Space Complexity

Now, let's discuss the time and space complexity of our efficient solution.

Time Complexity: The time complexity of this solution is O(log10(x)).

In the worst case, we iterate through the number's digits, and the number of iterations depends on the number of digits in x.

Space Complexity: The space complexity is O(1) because we only use a few extra variables, and the memory usage doesn't depend on the input size.

Reasoning Behind Our Approach

The efficient approach we've discussed might seem a bit tricky at first, but it's based on a straightforward idea: we're essentially comparing the leftmost and rightmost digits of the number while removing them in each iteration.

We use the div variable to determine the scale of the left and right digits we need to compare.

Starting with div as 1, we multiply it by 10 until it's greater than or equal to ten times the input number x.

This step ensures that div is of the correct magnitude to extract the most significant digit.

Then, in each iteration, we compare the left and right digits, progressively moving towards the center of the number.

If at any point the digits are not equal, we return False, indicating that the number is not a palindrome.

Otherwise, we keep moving towards the center, continuously removing the left and right digits using mathematical operations.

The key insight here is that we're not converting the number to a string, and by managing div and extracting digits, we efficiently check for palindromes.

The code

might appear dense, but the underlying concept is straightforward and elegant.

Conclusion

In this blog post, we've explored the Palindrome Number problem from LeetCode.

We've provided both a brute-force approach and an efficient solution that doesn't involve converting the integer to a string.

The efficient solution leverages mathematical operations to compare the digits of the number while gradually reducing its size.

By understanding the problem's constraints, constraints, and reasoning behind our approach, you've gained valuable insights into how to approach similar coding challenges.

Now, it's your turn!

Give the code a try, and don't forget to test it with different inputs.

If you have any questions, suggestions, or want to share your thoughts, please leave a comment.

Happy coding!