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)