Reverse Integer

Difficulty: Medium Source: NeetCode

Problem

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³¹, 2³¹ - 1], 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

Example 4: Input: x = 1534236469 Output: 0 Explanation: Reversed integer 9646324351 overflows 32-bit range.

Constraints:

-2³¹ <= x <= 2³¹ - 1

Prerequisites

Before attempting this problem, you should be comfortable with:

Modulo operator (%) — extracts the last digit of a number
Integer division (//) — removes the last digit from a number
32-bit integer bounds — [-2147483648, 2147483647]
Python’s modulo behavior for negative numbers — Python’s % always returns a non-negative result, which differs from C/Java

1. Brute Force (String Reversal)

Convert to string, reverse it, check the sign, convert back. Strip the negative sign before reversing, then reapply it. The overflow check is easy — Python integers are unbounded so we just compare against the 32-bit limits before returning.

Algorithm

Record the sign of x.
Reverse the absolute value as a string.
Convert back to integer and reapply the sign.
Return 0 if the result is outside [-2³¹, 2³¹ - 1].

Solution

def reverse(x):
    sign = -1 if x < 0 else 1
    reversed_str = str(abs(x))[::-1]
    result = sign * int(reversed_str)
    if result < -(2**31) or result > 2**31 - 1:
        return 0
    return result


print(reverse(123))         # 321
print(reverse(-123))        # -321
print(reverse(120))         # 21
print(reverse(1534236469))  # 0
print(reverse(0))           # 0

Complexity

Time: O(log x) — proportional to number of digits
Space: O(log x) — for the string

2. Digit-by-Digit with Overflow Check

Intuition

Pop digits from the end of x one at a time and push them onto the reversed number. “Popping” a digit means taking x % 10 to get the last digit, then doing x //= 10 to discard it. “Pushing” means doing result = result * 10 + digit.

The tricky part is detecting overflow before it happens (since we can’t store 64-bit integers in the spirit of the problem). Check that result * 10 + digit won’t exceed the bounds before actually computing it.

Python note: Python’s % operator returns a non-negative result even for negative numbers — (-123) % 10 = 7 in Python, not -3. We handle the sign separately and work on abs(x).

For x = 123:

pop 3 → result = 3,   x = 12
pop 2 → result = 32,  x = 1
pop 1 → result = 321, x = 0
done

For x = 1534236469:

...at some point result will exceed 2147483647, so return 0

Algorithm

Determine the sign; work with x = abs(x).
Initialize result = 0 and INT_MAX = 2**31 - 1.
While x != 0:
- Pop the last digit: digit = x % 10, x //= 10.
- Before pushing, check overflow: if result > (INT_MAX - digit) // 10, return 0.
- Push: result = result * 10 + digit.
Return sign * result.

Solution

def reverse(x):
    INT_MAX = 2**31 - 1  # 2147483647
    INT_MIN = -(2**31)   # -2147483648

    sign = -1 if x < 0 else 1
    x = abs(x)
    result = 0

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

        # Check overflow before committing to the push.
        # result * 10 + digit > INT_MAX  iff  result > (INT_MAX - digit) / 10
        if result > (INT_MAX - digit) // 10:
            return 0

        result = result * 10 + digit

    return sign * result


print(reverse(123))         # 321
print(reverse(-123))        # -321
print(reverse(120))         # 21
print(reverse(1534236469))  # 0
print(reverse(0))           # 0
print(reverse(-2147483648)) # 0  (reversed would be 8463847412, overflows)

Complexity

Time: O(log x) — one iteration per digit
Space: O(1)

Common Pitfalls

Python’s negative modulo. (-7) % 10 in Python is 3, not -7. Always work with abs(x) and track the sign separately to avoid surprising results.

Off-by-one in the overflow check. The check result > (INT_MAX - digit) // 10 uses integer division. For INT_MAX = 2147483647: when digit = 7 and result = 214748364, we’d get result * 10 + digit = 2147483647 which is exactly INT_MAX — that’s fine! Only return 0 if it would strictly exceed the limit.

Not handling the minimum bound separately. INT_MIN = -2147483648 has a larger absolute value than INT_MAX = 2147483647. In Python, the sign * result at the end handles this correctly since Python supports arbitrary precision — the final comparison covers both bounds.

Keyboard shortcuts

Note Book