Reverse Integer

Problem Statement

You are given a signed 32-bit integer x.

Return x after reversing its digits. After reversing, if x goes outside the signed 32-bit integer range [-2^31, 2^31 - 1], then return 0 instead.

Solve the problem without using integers that are outside the signed 32-bit integer range.

Example 1:

Input: x = 1234
Output: 4321

Example 2:

Input: x = -1234
Output: -4321

Example 3:

Input: x = 1234236467
Output: 0

Constraints:

  • -2^31 <= x <= 2^31 - 1

The time complexity should be O(log(x)) and the space complexity should be O(1).

Hint 1

How would you extract the last digit of a number?

Hint 2

How can you build the reversed number digit by digit?

Hint 3

Consider the overflow conditions.

Solution

Brute Force

def reverse(x: int) -> int:
original = x
x = abs(x)
reversed_x = int(str(x)[::-1])
if original < 0:
reversed_x *= -1
if reversed_x < -(1 << 31) or reversed_x > (1 << 31) - 1:
return 0
return reversed_x

Time complexity: O(log(x)) Space complexity: O(1)

Recursion

def reverse(x: int) -> int:
def rec(n: int, rev: int) -> int:
if n == 0:
return rev
rev = rev * 10 + n % 10
return rec(n // 10, rev)
sign = -1 if x < 0 else 1
x = abs(x)
reversed_num = rec(x, 0)
reversed_num *= sign
if reversed_num < -(1 << 31) or reversed_num > (1 << 31) - 1:
return 0
return reversed_num

Time complexity: O(log(x)) Space complexity: O(log(x))

Iteration

import math
def reverse(x: int) -> int:
minimum = -2147483648 # -2^31,
maximum = 2147483647 # 2^31 - 1
result = 0
while x:
digit = int(math.fmod(x, 10))
x = int(x / 10)
if result > maximum // 10 or (result == maximum // 10 and digit > maximum % 10):
return 0
if result < minimum // 10 or (result == minimum // 10 and digit < minimum % 10):
return 0
result = (result * 10) + digit
return result

Time complexity: O(log(x)) Space complexity: O(1)