How to determine if a number is a Palindrome
Spoilers, 10 is not a palindrome.
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.
The implementation works with one-word strings but needs some modifications to work with the sentences. The transformations needed would be :
- Remove punctuations and special characters
- 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!
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
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
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)
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)
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)
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 :
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)
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
Yeap, that's all! You did it! I'm so proud of you! Thank you for being on this adventure with me.
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!