Practice Algorithms with Math Puzzles Part 1
Hello, we are gonna solve a puzzle regarding palindrome numbers.
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
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
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.