Reverse Integer

Problem

https://leetcode.com/problems/reverse-integer/

Given a signed 32-bit integer x, return x with its digits reversed. If reversing x causes the value to go outside the signed 32-bit integer range [-2:sup:`31`, 2:sup:`31`- 1], then return 0.

Assume the environment does not allow you to store 64-bit integers (signed or unsigned).

Example 1:

Input: x = 123
Output: 321

Example 2:

Input: x = -123
Output: -321

Example 3:

Input: x = 120
Output: 21

Constraints:

• -2:sup:`31`<= x <= 2:sup:`31`- 1

Pattern

Math

Solution

Extract the sign of x. We can use modulus and division to get the digits of x. Reverse the list of digits. Then check that the digits are in the range \([2^{31} - 1, -2^{31}]\). If so, calculate the reversed integer using the expansion

\[\begin{split}r = \\sum_{i=0}^{n-1} 10^i d_i.\end{split}\]

Code

def reverse(x: int) -> int:
    sign = 1 if x > 0 else -1
    x = sign * x

    digits = []
    while x > 0:
        remainder = x % 10
        digits.append(remainder)
        x = x // 10

    digits = digits[::-1]

    if too_large(sign, digits):
        return 0
    else:
        r = 0
        for i, digit in enumerate(digits):
            r += digit * 10**i
        return sign * r


def too_large(sign, digits):
    if len(digits) < 10:
        return False

    if len(digits) > 10:
        return True

    tl = False
    limit = 2**31 - 1 if sign == 1 else 2**31
    for digit in enumerate(digits):
        limit_digit = limit % 10
        if digit > limit_digit:
            tl = True
        elif digit < limit_digit:
            tl = False

        limit = limit // 10

    return tl

Test

>>> from reverse_integer__approach_1 import reverse
>>> reverse(123)
321
>>> reverse(-123)
-321
>>> reverse(120)
21

Complexity

Time: \(O(\log_{10} x)\) — extract each digit, reverse list of digits, and calculate reversed integer

Auxiliary Space: \(O(\log_{10} x)\) — digits list

reverse_integer__approach_1.reverse(x: int) → int

reverse_integer__approach_1.too_large(sign, digits)