Palindrome Number | Different techniques for detection

Palindrome is a number which is same if you read if from left to right or from right to left.

For example, 121 does not matter from which side you start reading it, it will remain same - 121.

The problem statement looks like this:
An integer is a palindrome when it reads the same backward as forward.
Given an integer x, return true if x is palindrome integer.

Whenever you encounter a problem don't jump right into the solution, instead try to think it through, try to think about the different edge cases of the problem. For example in this one, you can ask the interviewer the following questions to clarify more:

• If number 0 is a palindrome? or All one digit numbers are palindrome or not?
• What about negative numbers? for example 121 is palindrome but what about -121? it will not be palindrome considering the negative sign.

Let's assume the interviewer clarify these questions like this:

• All one digit numbers are not palindrome.
• All negative numbers are not palindrome.

Now let's jump right into the solution.

First Technique

The first solution which comes to almost everyone's mind is:

• Convert the number into string.
• Reverse the string and compare both strings.

class Solution:
    def isPalindrome(self, x: int) -> bool:
        xString = str(x)
        return xString == xString[::-1]

This solution is actually correct but it requires some extra memory to create the string and the interviewer can put a restriction not to use any extra space. So in that case this solution won't be the best one to have.

Second Technique

In order to avoid the non-constant extra space usage what we can do is:

• Revert the integer itself
• And compare the integer with reverted one So how can we do that?

Let's try to see with an example 5445.
In mathematics we know we can get the last digit of a number by taking a 10 modulus so we keep taking the modulus and adding the number in reverted number and we will have the reverted number. And we will only revert positive numbers as we don't care about the negative ones in this case.

Python code looks like this to revert a positive number.

def revertNumber(x: int) -> int:
    if x < 0:
        raise ValueError('Only positive integers are allowed') 

    revertedNumber = 0

    while(x > 0):
        revertedNumber = revertedNumber * 10 + x % 10
        x = x // 10

    return revertedNumber

As we now have a function to revert the number so we can use this function to detect Palindromes.

def isPalindrome(x: int) -> bool:
    return x == revertNumber(x)

Final Approach

So now we have a solution which is more efficient than creating and reverting a string.

But.... we have a small issue with this problem if the reversed number is larger than int.MAX, we will hit integer overflow problem.

In order to avoid this situation we can change our solution a bit, instead of reversing the whole number we can just reverse the half of the number and compare it with the first half of the original number. For example:

• 5445, if we reverse the half number that would 54.
• Now if we compare this 54 it's same as the first half of the number so this is a Palindrome.

def isPalindrome(x: int) -> bool:
    # Special cases:
    # As discussed above, 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

    revertedNumber = 0

    while(x > revertedNumber):
        revertedNumber = revertedNumber * 10 + x % 10
        x //= 10

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

Complexity Analysis

Time complexity: O(log10(n)). We divided the input by 10 for every iteration, so the time complexity is O(log10(n))

Space complexity: O(1)