Published in



Practice Algorithms with Math Puzzles Part 1

Hello, we are gonna solve a puzzle regarding palindrome numbers.

Photo by Alvaro Reyes on Unsplash

A palindrome number is read the same backwards like 121 or 1221.

Let’s see how to write an algorithm that returns true if a positive integer is palindrome and false otherwise. I’m using python language. there are different ways of doing so but we want to come up with an algorithm with linear time complexity which means the running time of it should increase linearly versus the number of digits of the input. I’m using python language. we should check if the number is equal to it’s reverse.

Method 1: without conversion to string

The while loop creates the reverse of input and the best thing is to trace the loop for an small input like 121 with our good friends pen and paper.

If k is the number of digits in input:

The number of the while loop iterations = k

The number of comparisons in line 8 = k

so the total running time of function would be linear versus k.

Method 2: conversion to string

def func(n):
x= str(n)
return x==x[::-1]

The str() is a python built-in function that converts the given object to string.

x[::-1] means we subset the string from last to first item so gives the reverse but x[:] means to subset from first to last item so just gives the string itself.

Comparing running times

import time
s = time.time() # storing current time in s
func(10**10+1) # passing it a palindrome number
e = time.time() # storing current time in e
print(e-s) # printing the running time

Applying the above code for both methods showed me that method 2 is faster than method 1.

Thanks for reading.



Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Sepehr Vafaei

Sepehr Vafaei


I write mentally and financially helpful content for a peaceful productive life. Trader, Blogger, Investor. BC, Canada. Twitter: