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

Approaches

Digit Extraction

Explanation

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__digit_extraction import reverse
>>> reverse(123)
321
>>> reverse(-123)
-321
>>> reverse(120)
21

Complexity

Measure	Complexity	Notes
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__digit_extraction.reverse(x: int) → int

reverse_integer__digit_extraction.too_large(sign, digits)