November 01, 2018
Write a program which determines if the decimal representation of an integer is a palindromic string. For example, your program should return true for the inputs 0, 1, 7, 11, 121, 333, and 2147447412, and false for the inputs -1, 12, 100, and 2147483647.
def is_palindrome(integer): if integer < 0: return False elif integer < 10: return True else: return str(integer) == str(integer)[::-1]:
is_palindrome(2147447412) ===> True Input is not less than 0, so it will go through the next lines of code. "2147447412" == "2147447412" So this returns True.
Big O of reversing by slicing is O(n), where n is the number of digits of the input.
But according to the book, “Elements of Programming Interviews in Python” (EPI from here on), we can optimize this by directly extracting the digits.
First you have know how to compute the number of digits of the input. There are also ways to determine the first and last digits. As well as how to remove them so that you’re left with the remaining digits. If you know all these, you’re golden!
How to come up with the total number of digits in a number:
Find out the log base 10 of the number and add 1. For example: to calculate the total number of digits in 323, you do math.floor of , and then add 1. This will give you 3.
How to calculate the first digit:
Do an integer division of the number by a certain divisor such that it gives the first digit. For example, what would we use so we can get 3 from the number 323? Divide by 100 and disregard the remainder (we can do this using integer division, ”//” in Python). But how can we get 100? Well, above, we have . So for the number 323, we get 2.51 but remove the .51 using math.floor. Then raise 10 by it: . Now, we can do .
How to calculate the last digit:
Get the mod of the number by 10:
323 % 10 = 3
The next step is to determine if these two digits are the same. If the number is 324, it’s not, so we just return False. But for 323, it is True, so we go to the next step.
We then have to drop these two digits from the number. How? Get the mod of the number by the same divisor calculated from determining the first digit.
323 % 100 = 23
Then, remove the last digit by integer division by 10.
23 // 10 = 2
Check if number of digits remaining using . In the case of any number less than 10, the result is less than 1, so we stop, and return true. Else, if it’s less than 2 but greatern than 1, it means there are two digits remaining.
…to be continued.