AV's Blog

Reverse Digits

November 01, 2018

The following is a practice interview question taken out of the book, “Elements of Programming Interviews in Python”.

Write a program which takes an integer and returns the integer corresponding to the digits of the input written in reverse order. For example, the reverse of 42 is 24, and the reverse of -314 is -413.

Brute-force approach:

def reverse(num):
  tmp = str(num)
  if num < 0:
    tmp = tmp[1:]
    tmp2 = tmp[::-1]
    tmp2 = "-" + tmp2
  else:
    tmp2 = tmp[::-1]
  return int(tmp2)

Another approach is not having to convert the number into a string.

For example, consider the number 1132. The first digit is 2, which is the result of getting the modulo 10 of 1132. The remaining digits are 113 which is the result of integer division by 10 of the original number. This result of integer division can then obtained for its module 10 again, resulting to 3. To “append” this to 2, you multiply 2 by 10 and add 3 to get 23 as a number.

This just repeats until there is no remaining digits from integer division.

Pseudo code

  1. Obtain the absolute of the input number.
  2. Obtain the mod 10 of the number
  3. The result should be placed in a holder.
  4. Do integer division by 10 of the number, giving the remaining numbers without the last digit.
  5. Multiply the result from #3 by 10 and add the modulo 10 result from previous round. (for the first round, result is set to 0.)
  6. Repeat from #2 until the result of the integer division by 10 is 0.

Implementation

def reverse(num):
  remaining = abs(num)
  result = 0
  while remaining:
    result = (remaining % 10) + result * 10
    remaining = remaining // 10
  if num < 0:
    result = - result
  return result

Test

reverse(1132) ===> 2311

remaining = abs(1132) = 1132
result = 0
round 1:
  since remaining isn't 0:
    result = (1132 % 10) + 0 = 2
    remaining = 1132 // 10 = 113
round 2:
  remaining isn't 0:
    result = (113 % 10) + 2 * 10 = 3 + 20 = 23
    remaining = 113 // 10 = 11
round 3:
  remaining isn't 0:
    result = (11 % 10) + 230 = 231
    remaining = 11 // 10 = 1
round 4:
  remaining isn't 0:
    result = (1 % 10) + 2310 = 2311
    remaining = 1 // 10 = 0
round 5?
  remaining is 0 so loop is broken.

result is 2311 will be returned, since num is greater than 0.

Time complexity of the code is O(n) where n is the number of digits.