LeetCode #7 Medium

Reverse Integer

Q: Why compare rev with INT_MAX / 10 in the reverse integer LeetCode solution?

Because the next step multiplies rev by 10. If rev is already larger than INT_MAX / 10, that product is larger than INT_MAX, so you can return 0 without computing it. Dividing the limit instead of multiplying rev keeps every number in range.

Reverse Integer is LeetCode 7 (Medium). You are given a signed 32-bit integer x. Return x with its decimal digits in reverse order, keeping the sign.

If the reversed value falls outside the signed 32-bit range, from −2³¹ to 2³¹ − 1, return 0.
Assume the environment cannot store 64-bit integers, so you may not reverse into a wider type and range-check at the end.
Zeros that end up in front after reversing disappear, as they would in any integer.

x has at most 10 digits, so the work is tiny; the whole difficulty is the overflow rule.

Constraints

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

mathoverflow

Open on LeetCode ↗

02

Intuition

Reversing needs only two arithmetic moves, repeated until nothing is left: pop the last digit with % 10 and // 10, then push it onto the result with rev * 10 + digit. The digit popped first ends up leftmost, because every later push shifts it one place further left.

The catch is the push. rev * 10 is the step that can leave the 32-bit range, and in C++ or Java the value has already wrapped by the time you could look at it. So the overflow test has to be asked before the multiply, using numbers that are still in range: compare rev with the limit divided by 10.

How to spot this pattern

Any digit-by-digit problem on a bounded integer (reverse integer, palindrome number, string to integer) uses the same pair: % 10 to read the lowest digit and // 10 to remove it, with an overflow guard placed before every * 10.

03

Approach

Try it first

Before reading on, write the pop/push loop and decide exactly which comparison, made before rev * 10, proves the next push would overflow. Then check whether you also need to compare the digit. Aim for O(log x) time and O(1) space.

Two ways to solve it

Pop and push digitsBest

Time O(log x)Space O(1)

Peel digits off with % 10 and / 10, build rev with * 10, and stop with 0 the moment a push would overflow.

Memory: three integers.
Rule: never needs a 64-bit value.
Interview: the version that is asked for.

The answer the problem is testing.

Solution & demo ↓

Reverse the string

Time O(log x)Space O(log x)

Turn |x| into a string, reverse it, parse it back into a wider type, then range-check and restore the sign.

Memory: a string of up to 10 digits.
Rule: relies on a 64-bit or unbounded value.
Code: short and hard to get wrong.

Accepted, but not what interviewers want.

Code ↓

Both touch each digit once, but only the digit loop respects the rule against storing 64-bit values. The steps, code and live demo below follow it; the string code comes after the demo.

1

Split off the sign (Python)

In a reverse integer Python solution, % and // round toward negative infinity, so -123 % 10 is 7, not -3. Remember sign, reverse abs(x), and multiply the sign back at the end.

2

Pop, guard, push

While x is not 0, take digit = x % 10 and x //= 10. If rev > 214748364 (that is 2147483647 // 10), return 0, because multiplying by 10 must overflow. Otherwise rev = rev * 10 + digit.

3

Why the digit never needs checking

If rev is below 214748364, then rev * 10 + 9 is at most 2147483639, inside the range. If rev equals 214748364, the push is the tenth digit, which is the first digit of a 10-digit x. A 32-bit x with 10 digits starts with 1 or 2, so the result is at most 2147483642. Only rev > 214748364 can overflow.

4

Negative numbers in C++ and Java

There % and / truncate toward zero, so -123 % 10 is -3 and the same loop builds -321 with no sign handling. The guard just needs a mirror: return 0 if rev < INT_MIN / 10 as well. Avoid abs(x) there: abs(-2147483648) itself overflows.

04

Reverse Integer solution in Python | C++ | Java

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

x123

sign1positive

limit214748364(2³¹ − 1) // 10

Plan. Read digits from the right with % 10 and append each to rev. The limit 214748364 is INT_MAX with its last digit dropped: any rev above it would overflow when multiplied by 10.

digit3x % 10

x12x // 10

x % 10 reads the last digit, 3, and x //= 10 removes it from x. It is the next digit to go on the right of rev.

digit3

rev3was 0

The guard passes (0 is not above the limit), so multiply rev by 10, which shifts every digit one place left, and add 3 in the free units place. rev is now 3.

digit2x % 10

x1x // 10

x % 10 reads the last digit, 2, and x //= 10 removes it from x. It is the next digit to go on the right of rev.

digit2

rev32was 3

The guard passes (3 is not above the limit), so multiply rev by 10, which shifts every digit one place left, and add 2 in the free units place. rev is now 32.

digit1x % 10

x0x // 10

x % 10 reads the last digit, 1, and x //= 10 removes it from x. It is the next digit to go on the right of rev.

digit1

rev321was 32

The guard passes (32 is not above the limit), so multiply rev by 10, which shifts every digit one place left, and add 1 in the free units place. rev is now 321.

rev321

result321fits in 32 bits

x is 0, so every digit has moved. The answer is 321.

x1534236469

sign1positive

limit214748364(2³¹ − 1) // 10

Plan. Read digits from the right with % 10 and append each to rev. The limit 214748364 is INT_MAX with its last digit dropped: any rev above it would overflow when multiplied by 10.

digit9

rev9was 0

Pop 9 from the end of x. The guard passes (0 is not above the limit), so multiply rev by 10, which shifts every digit one place left, and add 9 in the free units place. rev is now 9.

digit6

rev96was 9

Pop 6 from the end of x. The guard passes (9 is not above the limit), so multiply rev by 10, which shifts every digit one place left, and add 6 in the free units place. rev is now 96.

digit4

rev964was 96

Pop 4 from the end of x. The guard passes (96 is not above the limit), so multiply rev by 10, which shifts every digit one place left, and add 4 in the free units place. rev is now 964.

digit6

rev9646was 964

Pop 6 from the end of x. The guard passes (964 is not above the limit), so multiply rev by 10, which shifts every digit one place left, and add 6 in the free units place. rev is now 9646.

digit3

rev96463was 9646

Pop 3 from the end of x. The guard passes (9646 is not above the limit), so multiply rev by 10, which shifts every digit one place left, and add 3 in the free units place. rev is now 96463.

digit2

rev964632was 96463

Pop 2 from the end of x. The guard passes (96463 is not above the limit), so multiply rev by 10, which shifts every digit one place left, and add 2 in the free units place. rev is now 964632.

digit4

rev9646324was 964632

Pop 4 from the end of x. The guard passes (964632 is not above the limit), so multiply rev by 10, which shifts every digit one place left, and add 4 in the free units place. rev is now 9646324.

digit3

rev96463243was 9646324

Pop 3 from the end of x. The guard passes (9646324 is not above the limit), so multiply rev by 10, which shifts every digit one place left, and add 3 in the free units place. rev is now 96463243.

digit5

rev964632435was 96463243

Pop 5 from the end of x. The guard passes (96463243 is not above the limit), so multiply rev by 10, which shifts every digit one place left, and add 5 in the free units place. rev is now 964632435.

digit1x % 10

x0x // 10

result0would overflow

Overflow, caught early. rev is 964632435, already above 214748364. Multiplying it by 10 would give at least 9646324350, past 2147483647, so return 0 without doing the multiply. In C++ or Java the multiply itself would have wrapped.

x1463847412

sign1positive

limit214748364(2³¹ − 1) // 10

Plan. Read digits from the right with % 10 and append each to rev. The limit 214748364 is INT_MAX with its last digit dropped: any rev above it would overflow when multiplied by 10.

digit2

rev2was 0

Pop 2 from the end of x. The guard passes (0 is not above the limit), so multiply rev by 10, which shifts every digit one place left, and add 2 in the free units place. rev is now 2.

digit1

rev21was 2

Pop 1 from the end of x. The guard passes (2 is not above the limit), so multiply rev by 10, which shifts every digit one place left, and add 1 in the free units place. rev is now 21.

digit4

rev214was 21

Pop 4 from the end of x. The guard passes (21 is not above the limit), so multiply rev by 10, which shifts every digit one place left, and add 4 in the free units place. rev is now 214.

digit7

rev2147was 214

Pop 7 from the end of x. The guard passes (214 is not above the limit), so multiply rev by 10, which shifts every digit one place left, and add 7 in the free units place. rev is now 2147.

digit4

rev21474was 2147

Pop 4 from the end of x. The guard passes (2147 is not above the limit), so multiply rev by 10, which shifts every digit one place left, and add 4 in the free units place. rev is now 21474.

digit8

rev214748was 21474

Pop 8 from the end of x. The guard passes (21474 is not above the limit), so multiply rev by 10, which shifts every digit one place left, and add 8 in the free units place. rev is now 214748.

digit3

rev2147483was 214748

Pop 3 from the end of x. The guard passes (214748 is not above the limit), so multiply rev by 10, which shifts every digit one place left, and add 3 in the free units place. rev is now 2147483.

digit6

rev21474836was 2147483

Pop 6 from the end of x. The guard passes (2147483 is not above the limit), so multiply rev by 10, which shifts every digit one place left, and add 6 in the free units place. rev is now 21474836.

digit4

rev214748364was 21474836

Pop 4 from the end of x. The guard passes (21474836 is not above the limit), so multiply rev by 10, which shifts every digit one place left, and add 4 in the free units place. rev is now 214748364.

digit1

rev2147483641was 214748364

Pop 1 from the end of x. rev equals the limit exactly, which is not above it. This is the tenth digit, so it is the first digit of x and at most 2: the result, 2147483641, still fits.

rev2147483641

result2147483641fits in 32 bits

x is 0, so every digit has moved. The answer is 2147483641. It sits just under 2147483647, and no 64-bit value was ever needed to prove it.

05

String reversal

The digits of |x| are reversed as text and parsed back into a type wider than 32 bits, so the range check can happen after the fact. The sign is put back last.

▶1class Solution:
▶2    def reverse(self, x: int) -> int:
▶3        sign = -1 if x < 0 else 1
▶4        rev = sign * int(str(abs(x))[::-1])
▶5        if rev < -(2**31) or rev > 2**31 - 1:
▶6            return 0
▶7        return rev

06

Common pitfalls

Checking for overflow after the multiply

✗ Wrong

rev = rev * 10 + digit
if rev > INT_MAX:
    return 0

✓ Right

if rev > INT_MAX / 10:
    return 0
rev = rev * 10 + digit

In C++ and Java a 32-bit rev can never be greater than INT_MAX; the multiply has already wrapped to some other value, often negative. The comparison must be made on the old rev, against the limit divided by 10.

Using % on a negative number in Python

✗ Wrong

digit = x % 10  # x = -123 gives 7

✓ Right

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

Python's modulo takes the sign of the divisor, so negative inputs produce the wrong digits and x //= 10 never reaches 0 (it gets stuck at -1). Reversing the absolute value avoids both.

Reversing into a long and checking at the end

✗ Wrong

long rev = 0;
...
return rev > INT_MAX ? 0 : (int) rev;

✓ Right

int rev = 0;
... guard before each push ...

It passes the tests, but the problem rules out 64-bit storage, and interviewers ask for the in-range check specifically. It is the first follow-up you will get.

07

Edge cases

Trailing zeros, like 120

The first pop gives 0 and rev stays 0, so the zero vanishes and 120 becomes 21. No special code is needed.

Reversal that overflows, like 1534236469

After nine pushes rev is 964632435, above 214748364, so the guard returns 0 before the tenth push.

−2147483648, the smallest int

In Python abs is safe and the reversal 8463847412 trips the guard. In C++ and Java the loop never calls abs, so the extreme value is handled like any other negative and also returns 0.

08

Complexity

Time

O(log x)

Space

O(1)

One loop iteration per decimal digit, at most 10 for a 32-bit input. Only rev, digit and the sign are stored.

09

Reverse Integer FAQ

Why compare rev with INT_MAX / 10 in the reverse integer LeetCode solution?

Because the next step multiplies rev by 10. If rev is already larger than INT_MAX / 10, that product is larger than INT_MAX, so you can return 0 without computing it. Dividing the limit instead of multiplying rev keeps every number in range.

10

Reverse Integer

Intuition

Approach

Two ways to solve it

Split off the sign (Python)

Pop, guard, push

Why the digit never needs checking

Negative numbers in C++ and Java

Reverse Integer solution in Python | C++ | Java

String reversal

Common pitfalls

Checking for overflow after the multiply

Using % on a negative number in Python

Reversing into a long and checking at the end

Edge cases

Complexity

Reverse Integer FAQ

Related Maths problems

Count Primes

Factorial Trailing Zeroes

Fraction to Recurring Decimal

Integer Break

Multiply Strings

Excel Sheet Column Number

Study the complete Maths learning path

Understand the techniques behind this problem