Checking If the Decimal Integer is a Palindrome

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.

Talking it out

• If the integer is from 0 to 9, it is palindromic.
• If the integer is less than 0, it is not palindromic
• For integers from 10 to 99, it is only palidromic if it’s a multiple of 11.
• Brute force would be to take the string of the integer and see if the string is the same as the reverse of the string, which can be obtained using slice: string[::-1]

Brute force approach

def is_palindrome(integer):
  if integer < 0:
    return False
  elif integer < 10:
    return True
  else:
    return str(integer) == str(integer)[::-1]:

Test

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 $log\_{10} 323$, 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 $log\_{10} (number)$. So for the number 323, we get 2.51 but remove the .51 using math.floor. Then raise 10 by it: $10^2 = 100$. Now, we can do $324 // 100 = 3$.

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 $log\_{10}$. 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.