How to determine if a number is a Palindrome

How to determine if a number is a Palindrome

Spoilers, 10 is not a palindrome.

·

8 min read

A palindrome is a word or number that reads the same forward and backwards.

A few examples of palindromes are :

- Madam
- Hannah
- Bob
- Never odd or even
- A man, a plan, a canal – Panama
- 121
- 99
- 22

When dealing with strings, it's rather straightforward. The reverse of the string should be equal to the original string.

An implementation of this in python, is as shown below

original_string = "Madam"
original_string = original_string.lower() # convert to lowercase
string_reversed = "".join(reversed(original_string))

Comparing both variables yields true.

1.JPG The implementation works with one-word strings but needs some modifications to work with the sentences. The transformations needed would be :

  1. Remove punctuations and special characters
  2. Remove all spaces

The transformations are done using regex. Code implementation for these transformations is as shown below

import re # import regex

original_sentence = "A man, a plan, a canal – Panama "
original_sentence = original_sentence.lower() # convert to lowercase
original_sentence = re.sub('[^A-Za-z0-9]+', '', original_sentence) # remove all special characters and spaces
sentence_reversed = "".join(reversed(original_sentence))

Wait, but you said this is about numbers!

Buckle up, boys! A palindrome adventure awaits!

via GIPHY

The goal is to avoid converting the integer into a string to check if it qualifies as a palindrome. A few base cases we need to cover:

1 . Negative numbers cannot be palindromes

-121 -> 121-

2 . 10 is not a palindrome. In fact, any number ending with a zero is not a palindrome. When the zero moves to the ones position, a new number is formed.

3 . All numbers between 0 and 9 are palindromes

1010 -> 0101 # not read as the same number

Implementation for the base cases :

def check_if_palindrome(x):
# check if negative
    if x < 0 :
      return "Not a palindrome"
# check if ends with zero
    if x % 10 == 0:
       return "Not a palindrome"
 # check if x is between 0 and 9
    if(x > 0 && x <10):
       return "Is palindrome"

The % in python is used to get the modulus. In layman's terms, the modulus returns the remainder when we perform division.

For example, the division of 12 by 10 yields 1.2. 2 is the remainder of the division. Thus if we perform 12 % 10, we get 2.

This concept will be the backbone of our implementation for finding palindromes.

A few more examples for clarity :

100 % 10 -> 0
11 % 10 -> 1
13 % 6 -> 1
22 % 4 -> 2

via GIPHY

Look at the following examples. Do you notice a pattern?

import math # math module in python

121  % 10 -> 1
math.floor(121 / 10 )-> 12 

1771 % 10 -> 1
math.floor(1771 / 10 -> 177

2442 % 10 -> 2
math.floor(2442 / 10) -> 244

396693 % 10 -> 3
math.floor(396693 / 10) -> 39669

120 % 10 -> 0
math.floor(120 / 10) -> 12

Using 10 as the modulo yields the last digit, while getting the floor of the division with 10 yields all digits with the last digit eliminated.

We can then use two variables to keep track of both halves of the digit. The idea is to have both halves and compare them. If they are the same when reversed, we can identify a palindrome.

Let's first look at the even number 396693. We need an algorithm that splits the number into two, such that :

half_one = 396
half_two = 396 # 693 reversed

Hence in the first iteration, we get :

import math # math module in python

half_one  = math.floor(396693 / 10)
half_two  = 396693 % 10

2.JPG

On the next iteration, we need to use the value in half_one (39669) and eliminate the 9 at the end. The 9 needs to move to half_two(3) and have the value in half_two bump up to 39.

We start with half_two since we need the current value in half_one. Performing the % on 39669 yields 9. To get half_one's value to 39, we first need to multiply it by 10 to get 30. Then add 9 to 30.

Lastly, we can floor half_one by 10 to get 3966 . Our code thus becomes:

import math # math module in python

half_one  = math.floor(396693 / 10)
half_two  = 396693 % 10

half_two  = half_two * 10 + half_one % 10 # need to use the current value of half_one before it is changed
half_one  = math.floor(half_one / 10)

3.JPG

Performing this operation one more time :


import math # math module in python

half_one  = math.floor(396693 / 10)
half_two  = 396693 % 10

half_two  = half_two * 10 + half_one % 10 # need to use the current value of half_one before it is changed
half_one  = math.floor(half_one / 10)


half_two  = half_two * 10 + half_one % 10 # need to use the current value of half_one before it is changed
half_one  = math.floor(half_one / 10)

4.JPG

At this point, we can check if half_one is equivalent to half_two. We can generalise this to work for any even number as :


half_one = 396693
half_two = 0 # initialise as 0

while half_one > half_two :
      half_two  = half_two * 10 + half_one % 10 # need to use the current value of half_one before it is changed
      half_one  = math.floor(half_one / 10)

print(half_one, half_two)

5.JPG When half_one and half_two are compared, we get a true value and conclude the number is a palindrome and vice versa.

Updating our palindrome function to accomodate even numbers :


def check_if_palindrome(x):
    # check if negative
    if x < 0 :
      return "Not a palindrome"

    # check if ends with zero
    if x % 10 == 0:
       return "Not a palindrome"

    # check if x is between 0 and 9
    if x > 0 and x <10:
       return "Is palindrome"

    # palindrome for even numbers
    half_one = x
    half_two = 0 # initialise as 0    
    while half_one > half_two :              
          half_two  = half_two * 10 + half_one % 10 # need to use the current value of half_one before it is changed
          half_one  = math.floor(half_one / 10)

    if half_one == half_two:
        return "Is palindrome"
    else:
        return "Not a palindrome"

We now need to cover base for odd numbers. Odd numbers are such that when the middle number is removed , we are left with an even number, and we repeat the process above for even numbers.

import math # math module in python

half_one  = math.floor(121/ 10)
half_two  = 121% 10

This yields :

6.JPG

Performing this operation again moves 2 to the second half. We want to always have the odd value on the second half. This ensures the code runs until all values omitting the middle value have been separated.

import math # math module in python

half_one  = math.floor(121/ 10)
half_two  = 121% 10

half_two  = half_two * 10 + half_one % 10 # need to use the current value of half_one before it is changed
half_one  = math.floor(half_one / 10)

7.JPG

At this point we need to drop the 2 on half_two and compare the values in half_one and half_two again to check if the number is a palindrome


import math # math module in python

half_one  = math.floor(121/ 10)
half_two  = 121% 10

half_two  = half_two * 10 + half_one % 10 # need to use the current value of half_one before it is changed
half_one  = math.floor(half_one / 10)

half_two = math.floor(half_two / 10)

At this point half_one and half_two only contain the value 1. Comparing them yields true which means 121 was a palindrome. This can be generalised as :


half_one = 121
half_two = 0 # initialise as 0

while half_one > half_two :


      half_two  = half_two * 10 + half_one % 10 # need to use the current value of half_one before it is changed
      half_one  = math.floor(half_one / 10)     

print(half_one, math.floor(half_two / 10) )

Hold up! We've seen this before! Therefore we can adjust our palindrome function to accommodate odd numbers as follows:


def check_if_palindrome(x):
    # check if negative
    if x < 0 :
      return "Not a palindrome"

    # check if ends with zero
    if x % 10 == 0:
       return "Not a palindrome"

    # check if x is between 0 and 9
    if x > 0 and x <10:
       return "Is palindrome"

    # palindrome for odd and  even numbers
    half_one = x
    half_two = 0 # initialise as 0    
    while half_one > half_two :              
          half_two  = half_two * 10 + half_one % 10 # need to use the current value of half_one before it is changed
          half_one  = math.floor(half_one / 10)

    if half_one == half_two or half_one == math.floor(half_two / 10) :
        return "Is palindrome"
    else:
        return "Not a palindrome"

Testing the handy dandy function

8.JPG

Yeap, that's all! You did it! I'm so proud of you! Thank you for being on this adventure with me.

via GIPHY

Perhaps now you're wondering, is this solution optimal? Space-time complexity? Worry not! I will be covering these complex topics in a future blog. So please subscribe to my newsletter or follow me here on hashnode to ensure you do not miss that!