LeetCode #7 Medium

Reverse Integer

Reverse the digits of a signed 32-bit integer, returning 0 if the reversed value falls outside the 32-bit range.

mathoverflow

02

Intuition

💡

The natural instinct is to build the whole reversed number, then check at the end whether it fits in 32 bits. That check is already too late. In C++ or Java the multiply has wrapped around by the time you look, so rev holds a garbage value and your comparison against INT_MAX is comparing against noise — the very number you are trying to detect has been destroyed by the operation that overflowed it. Python will not visibly bite you here, which is exactly why this problem is worth doing properly: the discipline is to test before the dangerous operation, not after. Ask instead: is rev already greater than INT_MAX // 10? If so, rev * 10 cannot possibly fit, and you bail without ever computing it. That is the invariant — at the top of every iteration, rev is guaranteed to be a legal 32-bit value, and each step only proceeds if it can prove the next one will be too.

03

Approach

1

Split off the sign and work with the magnitude

Reversing a negative number is the same operation as reversing its absolute value and then re-applying the minus. Peeling the sign off first means the digit loop deals only with non-negative arithmetic, which avoids the language-specific mess of how % and // behave on negative operands (Python floors, C truncates — a genuine source of wrong answers here). Remember the sign and restore it at the end.

2

Guard before the multiply, never after

The bound is INT_MAX = 2147483647, so INT_MAX // 10 = 214748364. Before executing rev = rev * 10 + d, check whether rev already exceeds that ceiling; if it does, the multiply alone overflows and you return 0. If rev equals the ceiling exactly, the multiply is fine but the appended digit could still push past — that is why the boundary case compares d against 7, the last digit of INT_MAX. Doing this check first is the entire point of the problem.

3

Peel and append until the source is empty

Each turn take d = n % 10, do rev = rev * 10 + d, then n //= 10. The digit moves from the back of n to the back of rev, which is precisely what reversal means. The loop ends when n hits 0, which happens after exactly as many turns as n has digits — at most 10 for a 32-bit value. Finally multiply by the saved sign and return.

04

Solution & live demo

python

▶1class Solution:
▶2    def reverse(self, x: int) -> int:
▶3        INT_MAX = 2147483647
▶4        sign = -1 if x < 0 else 1
▶5        n, rev = abs(x), 0
▶6        while n > 0:
▶7            d = n % 10
▶8            if rev > INT_MAX // 10 or (rev == INT_MAX // 10 and d > 7):
▶9                return 0
▶10            rev = rev * 10 + d
▶11            n //= 10
▶12        return sign * rev

05

Edge cases

Reversal overflows, e.g. 1534236469

The pre-multiply guard fires part-way through and returns 0 without ever producing the bad value.

Negative input, e.g. -321

Sign is stripped first, 321 is reversed to 123, and the minus is re-applied to give -123.

Trailing zeros, e.g. 1200

The zeros become leading zeros in rev, which numerically vanish — 1200 reverses to 21.

x = 0

The loop body never runs, rev stays 0, and 0 is returned unchanged.

06

Complexity

Time

O(log n)

Space

O(1)

One pass over the digits of x — at most 10 iterations for any 32-bit input — with only two integers held.