7. Reverse Integer

MediumMath

LeetCode ↗

Problem Idea Example Code Visual Complex Pitfalls

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:

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

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

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 peel off the last digit and append it to our answer.

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.

For negative numbers, the cleanest cross-language approach is to truncate x / 10 toward zero first, then recover the current digit with:

digit = x - next_x * 10

where next_x = trunc(x / 10). This gives the correct digit for both positive and negative numbers without relying on language-specific modulo behavior.

The algorithm repeatedly:

Checks if we can safely add another digit without overflow
Computes the truncated next value and current digit
Appends it to our result
Removes the last digit from the original number

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

Pattern 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:

Overflow Check: Before adding a new digit, we check if ans is within the safe range [trunc(mi / 10), trunc(mx / 10)]. If ans < trunc(mi / 10) or ans > trunc(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 ≥ trunc(mi / 10)
Extract Last Digit: We first compute next_x = trunc(x / 10), then recover the current digit with y = x - next_x * 10.

Example: if x = -123, then next_x = -12 and y = -123 - (-12 * 10) = -3.
Build Reversed Number: We append the digit to our result: ans = ans * 10 + y.
Remove Last Digit: We remove the processed digit from x by assigning x = next_x.

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:

Check overflow: Is ans in range [trunc(mi / 10), trunc(mx / 10)]?
- ans = 0 is in range [-214748364, 214748364] ✓
Compute next_x = trunc(-123 / 10) = -12
Extract digit: y = -123 - (-12 * 10) = -3
Build result: ans = 0 * 10 + (-3) = -3
Remove digit: x = next_x = -12

Iteration 2:

Check overflow: Is ans = -3 in range [-214748364, 214748364]? ✓
Compute next_x = trunc(-12 / 10) = -1
Extract digit: y = -12 - (-1 * 10) = -2
Build result: ans = -3 * 10 + (-2) = -30 + (-2) = -32
Remove digit: x = next_x = -1

Iteration 3:

Check overflow: Is ans = -32 in range [-214748364, 214748364]? ✓
Compute next_x = trunc(-1 / 10) = 0
Extract digit: y = -1 - (0 * 10) = -1
Build result: ans = -32 * 10 + (-1) = -320 + (-1) = -321
Remove digit: x = next_x = 0

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

For a positive example like x = 120:

First iteration: next_x = 12, digit = 0, ans = 0, x = 12
Second iteration: next_x = 1, digit = 2, ans = 2, x = 1
Third iteration: next_x = 0, digit = 1, ans = 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

1class Solution:
2    def reverse(self, x: int) -> int:
3        """
4        Reverses the digits of a 32-bit signed integer.
5        Returns 0 if the reversed integer overflows.
6      
7        Args:
8            x: A 32-bit signed integer
9          
10        Returns:
11            The reversed integer, or 0 if overflow occurs
12        """
13        result = 0
14      
15        # Define 32-bit integer boundaries
16        MIN_INT = -(2**31)      # -2147483648
17        MAX_INT = 2**31 - 1     # 2147483647
18      
19        while x != 0:
20            # Check for potential overflow before multiplying by 10
21            # Truncate the boundaries toward zero to match digit extraction
22            if result < int(MIN_INT / 10) or result > int(MAX_INT / 10):
23                return 0
24          
25            # Compute the truncated prefix and recover the current digit
26            next_x = int(x / 10)
27            digit = x - next_x * 10
28          
29            # Build the reversed number
30            result = result * 10 + digit
31          
32            # Remove the last digit from x
33            x = next_x
34          
35        return result
36

1class Solution {
2    /**
3     * Reverses the digits of a 32-bit signed integer.
4     * Returns 0 if the reversed integer would overflow.
5     * 
6     * @param x the integer to reverse
7     * @return the reversed integer, or 0 if overflow would occur
8     */
9    public int reverse(int x) {
10        int reversedNumber = 0;
11      
12        // Process each digit from right to left
13        while (x != 0) {
14            // Check for potential overflow before multiplying by 10
15            // Integer.MAX_VALUE = 2147483647, Integer.MIN_VALUE = -2147483648
16            if (reversedNumber > Integer.MAX_VALUE / 10 || reversedNumber < Integer.MIN_VALUE / 10) {
17                return 0;
18            }
19          
20            // Extract the last digit and add it to the reversed number
21            int lastDigit = x % 10;
22            reversedNumber = reversedNumber * 10 + lastDigit;
23          
24            // Remove the last digit from x
25            x = x / 10;
26        }
27      
28        return reversedNumber;
29    }
30}
31

1class Solution {
2public:
3    int reverse(int x) {
4        int reversedNumber = 0;
5      
6        // Process each digit of the input number
7        while (x != 0) {
8            // Check for potential overflow before multiplying by 10
9            // INT_MAX = 2147483647, INT_MIN = -2147483648
10            // If reversedNumber > INT_MAX/10, then reversedNumber * 10 will overflow
11            // If reversedNumber < INT_MIN/10, then reversedNumber * 10 will underflow
12            if (reversedNumber > INT_MAX / 10 || reversedNumber < INT_MIN / 10) {
13                return 0;
14            }
15          
16            // Extract the last digit and append it to the reversed number
17            int lastDigit = x % 10;
18            reversedNumber = reversedNumber * 10 + lastDigit;
19          
20            // Remove the last digit from the original number
21            x /= 10;
22        }
23      
24        return reversedNumber;
25    }
26};
27

1/**
2 * Reverses the digits of a 32-bit signed integer
3 * @param x - The integer to reverse
4 * @returns The reversed integer, or 0 if the result would overflow
5 */
6function reverse(x: number): number {
7    // Define 32-bit signed integer boundaries
8    const MIN_INT32: number = -(2 ** 31);
9    const MAX_INT32: number = 2 ** 31 - 1;
10  
11    let result: number = 0;
12  
13    // Process each digit from right to left
14    while (x !== 0) {
15        // Check for potential overflow before multiplying by 10
16        // Using bitwise OR with 0 (~~) to truncate towards zero
17        if (result < ~~(MIN_INT32 / 10) || result > ~~(MAX_INT32 / 10)) {
18            return 0;
19        }
20      
21        // Append the last digit of x to result
22        result = result * 10 + (x % 10);
23      
24        // Remove the last digit from x (truncate towards zero)
25        x = ~~(x / 10);
26    }
27  
28    return result;
29}
30

Visualization

AlgoMonster exclusive: step through the algorithm state, not just the final code.

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.

Pattern 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. Assuming Python `%` and `//` Match Truncation Toward Zero

Pitfall: Python's % and // behave differently from Java, C++, and TypeScript for negative numbers. -123 % 10 becomes 7, and -123 // 10 becomes -13, which does not match truncation toward zero.

# WRONG: This uses Python's floor-division behavior
digit = x % 10
x //= 10

Solution: Compute the truncated quotient first, then recover the digit from it:

# CORRECT: Mimic truncation toward zero
next_x = int(x / 10)
digit = x - next_x * 10
x = next_x

3. Using Simple Integer Division for Negative Numbers

Pitfall: Using x // 10 directly for negative numbers gives floor division, not truncation toward zero.

# WRONG: floor division rounds down
x = x // 10

Solution: Use a truncated quotient instead:

# CORRECT: truncate toward zero
next_x = int(x / 10)

4. Incorrect Boundary Check Formula

Pitfall: In Python, MIN_INT // 10 uses floor division, so it does not match the truncation-toward-zero logic used by the digit extraction step.

# WRONG: floor division changes the lower bound
if result < MIN_INT // 10 or result > MAX_INT // 10:
    return 0

Solution: Use truncated division for both bounds:

# CORRECT: match truncation toward zero
if result < int(MIN_INT / 10) or result > int(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

Ready to land your dream job?

Unlock your dream job with a 5-minute evaluator for a personalized learning plan!

Start Evaluator

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Tailor Your Study Plan: