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^31, 2^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

What is the best way to implement this in Python?

def reverse_integer(x):
    """Reverses a 32-bit signed integer.

    Args:
        x: The integer to reverse.

    Returns:
        The reversed integer, or 0 if the reversed value overflows.
    """
    sign = 1 if x >= 0 else -1
    x = abs(x)
    reversed_x = 0

    while x > 0:
        digit = x % 10
        x //= 10

        # Check for potential overflow before multiplying
        if reversed_x > 214748364 or (reversed_x == 214748364 and digit > 7):
            return 0
        if reversed_x < -214748364 or (reversed_x == -214748364 and digit < -8):
            return 0

        reversed_x = reversed_x * 10 + digit

    return sign * reversed_x

# Example Usage
print(reverse_integer(123))
print(reverse_integer(-123))
print(reverse_integer(120))
print(reverse_integer(1534236469)) # Example to demonstrate overflow handling

Explanation:

1. Determine the Sign:

• The sign of the integer is stored to preserve it after reversal. We use a variable sign to keep track of this.

1. Absolute Value:

• The absolute value of the integer is used for the reversal process to simplify the digit manipulation.

1. Reversal Process:

• The while loop extracts the last digit (x % 10) from the number.
• It checks for potential overflow before multiplying by 10 and adding the new digit.
• The reversed integer is constructed by multiplying the current reversed value by 10 and adding the extracted digit.

1. Overflow Check:

• Before constructing the reversed integer, a check is performed to ensure the new digit won't cause an overflow. Specifically:
  • If reversed_x is already greater than 214748364 (2147483647 / 10), adding another digit will definitely cause an overflow.
  • If reversed_x is equal to 214748364, we need to check if the new digit is greater than 7 (since the max positive value is 2147483647).

1. Return Value:

• The reversed integer is multiplied by the original sign to get the correct signed reversed integer.
• If an overflow is detected, the function returns 0.

Big O Analysis

Time Complexity:

• O(log(n)): The number of iterations in the while loop depends on the number of digits in the input integer x. The number of digits is proportional to the logarithm (base 10) of x. Therefore, the time complexity is logarithmic with respect to the input value.

Space Complexity:

• O(1): The algorithm uses a fixed number of variables (sign, reversed_x, digit) regardless of the input size. Thus, the space complexity is constant.

Edge Cases:

1. Positive Integer:

• Input: 123
• Output: 321

1. Negative Integer:

• Input: -123
• Output: -321

1. Trailing Zero:

• Input: 120
• Output: 21

1. Overflow:

• Input: 1534236469 (reversing results in 9646324351, which is greater than 2³¹ - 1)
• Output: 0

1. Negative Overflow:

• Input: -2147483648 (reversing results in -8463847412, which is less than -2³¹)
• Output: 0