Problem Description

You need to reverse the digits of a given 32-bit signed integer x.

For example:

• If x = 123, return 321
• If x = -123, return -321
• If x = 120, return 21

The key constraint is that the reversed integer must stay within the valid range for a 32-bit signed integer, which is [-2^31, 2^31 - 1] or [-2147483648, 2147483647]. If reversing the digits would cause the number to overflow (exceed this range), you should return 0 instead.

An important restriction is that you cannot use 64-bit integers to check for overflow - you must work within the constraints of 32-bit arithmetic. This means you need to detect potential overflow before it happens, rather than reversing first and then checking if the result is out of bounds.

The challenge lies in:

1. Extracting digits from the original number one by one
2. Building the reversed number by appending these digits
3. Checking for overflow before each digit is added to prevent going outside the 32-bit range
4. Handling both positive and negative numbers correctly

Intuition

To reverse an integer, we need to extract its digits from right to left and build a new number from left to right. The natural approach is to repeatedly take the last digit using the modulo operator (x % 10) and add it to our result.

The main challenge is detecting overflow without using 64-bit integers. We need to check if adding another digit would cause overflow before we actually add it.

Let's think about when overflow happens. If we have a partial result ans and want to add another digit y, the new value would be ans * 10 + y. This needs to stay within [-2^31, 2^31 - 1].

For positive numbers, we need: ans * 10 + y ≤ 2^31 - 1

Rearranging: ans ≤ (2^31 - 1 - y) / 10

Since y is at most 9, we can simplify our check to: ans ≤ (2^31 - 1) / 10

Similarly for negative numbers: ans ≥ -2^31 / 10

So before multiplying ans by 10 and adding the next digit, we check if ans is within the safe range [-2^31 / 10, (2^31 - 1) / 10]. If it's outside this range, multiplying by 10 would definitely cause overflow.

There's a subtle issue with negative numbers in Python: when we do x % 10 on a negative number, Python returns a positive remainder. For example, -123 % 10 = 7 (not -3). To handle this, when x is negative but the remainder is positive, we adjust by subtracting 10 to get the correct negative digit.

The algorithm repeatedly:

1. Checks if we can safely add another digit without overflow
2. Extracts the last digit (with adjustment for negatives)
3. Appends it to our result
4. Removes the last digit from the original number

This way, we build the reversed number digit by digit while ensuring we never overflow.

Learn more about Math patterns.

Solution Approach

We implement the solution using a mathematical approach that extracts digits one by one and builds the reversed number while checking for overflow.

First, we initialize our variables:

• ans = 0: stores the reversed number
• mi = -2^31 and mx = 2^31 - 1: the boundaries of 32-bit signed integer range

The main algorithm uses a while loop that continues as long as x is not zero:

1. Overflow Check: Before adding a new digit, we check if ans is within the safe range [mi // 10 + 1, mx // 10]. If ans < mi // 10 + 1 or ans > mx // 10, multiplying by 10 would cause overflow, so we return 0.

   The mathematical reasoning: For ans * 10 + y to not overflow:

   • Upper bound: ans * 10 + y ≤ mx implies ans ≤ mx // 10 (since y ≤ 9)
   • Lower bound: ans * 10 + y ≥ mi implies ans ≥ mi // 10 + 1 (accounting for negative remainder)

2. Extract Last Digit: We get the last digit using y = x % 10. However, Python's modulo operation with negative numbers needs special handling. When x < 0 but y > 0, we adjust by subtracting 10 from y to get the correct negative digit.

   Example: -123 % 10 = 7 in Python, but we want -3, so we do 7 - 10 = -3.

3. Build Reversed Number: We append the digit to our result: ans = ans * 10 + y.

4. Remove Last Digit: We remove the processed digit from x using x = (x - y) // 10. We subtract y first to ensure correct integer division for both positive and negative numbers.

The loop continues until all digits are processed (x becomes 0), and we return the reversed number ans.

The time complexity is O(log(x)) since we process each digit once, and the space complexity is O(1) as we only use a constant amount of extra space.

Example Walkthrough

Let's walk through reversing x = -123 step by step.

Initial Setup:

• x = -123
• ans = 0
• mi = -2147483648 (-2^31)
• mx = 2147483647 (2^31 - 1)

Iteration 1:

1. Check overflow: Is ans in range [mi // 10 + 1, mx // 10]?
   • ans = 0 is in range [-214748364, 214748364] ✓
2. Extract digit: y = -123 % 10 = 7 (Python's modulo behavior)
3. Adjust for negative: Since x < 0 and y > 0, adjust: y = 7 - 10 = -3
4. Build result: ans = 0 * 10 + (-3) = -3
5. Remove digit: x = (-123 - (-3)) // 10 = -120 // 10 = -12

Iteration 2:

1. Check overflow: Is ans = -3 in range [-214748364, 214748364]? ✓
2. Extract digit: y = -12 % 10 = 8
3. Adjust for negative: Since x < 0 and y > 0, adjust: y = 8 - 10 = -2
4. Build result: ans = -3 * 10 + (-2) = -30 + (-2) = -32
5. Remove digit: x = (-12 - (-2)) // 10 = -10 // 10 = -1

Iteration 3:

1. Check overflow: Is ans = -32 in range [-214748364, 214748364]? ✓
2. Extract digit: y = -1 % 10 = 9
3. Adjust for negative: Since x < 0 and y > 0, adjust: y = 9 - 10 = -1
4. Build result: ans = -32 * 10 + (-1) = -320 + (-1) = -321
5. Remove digit: x = (-1 - (-1)) // 10 = 0 // 10 = 0

Result: The loop ends since x = 0. Return ans = -321.

For a positive example like x = 120:

• First iteration: Extract 0, ans = 0, x = 12
• Second iteration: Extract 2, ans = 0 * 10 + 2 = 2, x = 1
• Third iteration: Extract 1, ans = 2 * 10 + 1 = 21, x = 0
• Result: 21

The overflow check prevents issues. For example, if we try to reverse 1534236469:

• After several iterations, we'd have ans = 964632435 and x = 1
• Before adding the last digit, we check: Is 964632435 in range [-214748364, 214748364]?
• No! 964632435 > 214748364, so multiplying by 10 would overflow
• Return 0 immediately

Solution Implementation

Time and Space Complexity

The time complexity is O(log |x|), where |x| is the absolute value of x. This is because the while loop iterates through each digit of the input number x. The number of digits in x is proportional to log₁₀(|x|), which can be expressed as O(log |x|). In each iteration, the algorithm performs constant-time operations: modulo operation, division, multiplication, and addition.

The space complexity is O(1). The algorithm only uses a fixed amount of extra space regardless of the input size. The variables ans, mi, mx, and y are the only additional variables created, and they don't scale with the input size. No additional data structures like arrays or recursive call stacks are used.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Overflow Detection Timing

Pitfall: Many developers check for overflow after performing the multiplication result * 10 + digit, but this defeats the purpose since the overflow has already occurred.

# WRONG: Checking after the operation
result = result * 10 + digit
if result > MAX_INT or result < MIN_INT:
    return 0

Solution: Always check BEFORE the multiplication to predict if overflow will occur:

# CORRECT: Check before the operation
if result > MAX_INT // 10 or (result == MAX_INT // 10 and digit > 7):
    return 0
if result < MIN_INT // 10 or (result == MIN_INT // 10 and digit < -8):
    return 0
result = result * 10 + digit

2. Mishandling Python's Modulo with Negative Numbers

Pitfall: Python's modulo operator behaves differently than C++ or Java. For negative numbers, x % 10 returns a positive value, which can lead to incorrect results.

# Example: -123 % 10 = 7 (not -3 as you might expect)
# WRONG: Using modulo directly without adjustment
digit = x % 10
result = result * 10 + digit  # This will give wrong sign

Solution: Adjust the digit when dealing with negative numbers:

# CORRECT: Adjust for negative numbers
digit = x % 10
if x < 0 and digit > 0:
    digit -= 10

3. Using Simple Integer Division for Negative Numbers

Pitfall: Using x // 10 directly for negative numbers can give unexpected results due to floor division rounding toward negative infinity.

# Example: -123 // 10 = -13 (rounds down)
# But after extracting digit 7, we have -123 - 7 = -130
# -130 // 10 = -13 (correct)

Solution: Subtract the extracted digit before division to ensure correct behavior:

# CORRECT: Subtract digit before division
x = (x - digit) // 10

4. Incorrect Boundary Check Formula

Pitfall: Using MIN_INT // 10 directly without adjustment for the lower bound can miss edge cases.

# WRONG: Simple division check
if result < MIN_INT // 10 or result > MAX_INT // 10:
    return 0

Solution: For the minimum boundary, use MIN_INT // 10 + 1 to account for the fact that the minimum value's absolute value is one greater than the maximum:

# CORRECT: Adjusted boundary check
if result < MIN_INT // 10 + 1 or result > MAX_INT // 10:
    return 0

5. Not Considering the Last Digit in Overflow Check

Pitfall: When result equals MAX_INT // 10 or MIN_INT // 10, the last digit determines whether overflow occurs, but this is often overlooked.

Solution: For precise overflow detection at the boundary:

# More precise check (alternative approach)
if result > MAX_INT // 10:
    return 0
if result == MAX_INT // 10 and digit > MAX_INT % 10:
    return 0
# Similar logic for MIN_INT