The problem
Reverse the digits of a 32-bit signed integer. If the result would overflow the 32-bit range, return 0.
Input: −123 Output: −321
Picture it
Picture an odometer spinning backwards. Remember the sign, then repeatedly take the last digit (x mod 10), drop it from x, and append it to the result (result × 10 + digit). Before each append we check whether the result would go past the 32-bit limit; if so, the answer is 0.
How to recognise it
- You must rearrange the decimal digits of a number: reverse them.
x % 10reads the last digit andx // 10removes it, so digits can be taken off one at a time without strings.- Building the answer with
out * 10 + digitappends a digit on the right, which reverses the order. - The twist is the 32-bit limit: if the reversed number is outside −2^31 to 2^31 − 1, return 0. The input itself is always inside that range.
Start with brute force
Turn the number into text, reverse the text, and turn it back, keeping the sign apart.
def reverse_brute(x):
sign = -1 if x < 0 else 1
out = sign * int(str(abs(x))[::-1])
return out if -2**31 <= out < 2**31 else 0
It is correct and O(d) for d digits (at most 10), so it is not slow. Leading zeros vanish on their own: "021" reads back as 21. Interviewers usually want the arithmetic version, and the problem adds a rule (below) that the string approach also ignores.
From brute force to the idea
- Find the waste. The string detour converts every digit to a character and back; arithmetic can move digits directly.
- Handle the sign once. Python's
%and//round towards minus infinity, so-123 % 10is 7, not 3. The shown code saves the sign and works onabs(x), where both behave as expected. - Move digits across. Each round takes the last digit (
x % 10), appends it toout(out * 10 + digit), and removes it from x (x //= 10). When x reaches 0 every digit has moved. - Check the range. Restore the sign, then return 0 if the result is outside −2^31 to 2^31 − 1.
This is the key idea: pop the last digit with % 10 and push it with * 10 +, then check the 32-bit range.
The problem statement says to assume the machine cannot store 64-bit integers. The shown code does not follow that rule: it builds the full reversed value (up to 10 digits, such as 9,646,324,351) and only then compares, which is fine in Python because integers have no size limit. In Java or C++, check before each step instead: if out > (2^31 − 1) // 10, the next out * 10 would overflow, so return 0.
The key idea
Pop and push digits with % and //, checking against 2³¹ − 1 before each push.
Python solution
def reverse(x):
sign = -1 if x < 0 else 1
x, out = abs(x), 0
while x:
out = out * 10 + x % 10 # move the last digit over
x //= 10
out *= sign
return out if -2**31 <= out < 2**31 else 0In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.
Complexity
| Approach | Time | Space |
|---|---|---|
| Brute force (string reverse) | O(d): build, reverse and parse d characters, d ≤ 10 | O(d): the string |
| Digit loop (shown code) | O(d): one round per digit | O(1): two integers |
Edge cases
- Trailing zeros (
120): returns 21. - Zero: the loop never runs; returns 0.
- Negative (
-123): returns −321. - Overflow (
1534236469): the reverse 9,646,324,351 is too big, so it returns 0. - Smallest integer (
-2147483648): the reverse −8,463,847,412 is too small; returns 0. - Just inside the range (
1463847412): returns 2,147,483,641, which fits.
Common mistakes
- Using
%and//directly on a negative number in Python:-123 // 10is −13, and-1 // 10is −1, sowhile x:never ends. - Checking the range against the input instead of the reversed result.
- In fixed-width languages, multiplying first and checking afterwards, when the overflow has already happened.
- Converting through a string and forgetting the minus sign, so
int("321-")raisesValueError.
Decide whether an integer reads the same forwards and backwards (LeetCode 9), without converting it to a string. 121 is a palindrome, −121 and 10 are not. Describe your approach, then write it if you like.
Compare with our answer
Reverse only the second half of the digits and compare it with the first half; this never builds a number larger than the input. Negative numbers and numbers ending in 0 (other than 0 itself) cannot be palindromes.
def is_palindrome(x):
if x < 0 or (x % 10 == 0 and x != 0):
return False
half = 0
while x > half:
half = half * 10 + x % 10
x //= 10
return x == half or x == half // 10 # odd length: drop the middle digit
Time O(d), space O(1).
A strong answer mentions: reusing the pop-and-push digit loop, stopping at the middle, the odd-length case, and why trailing zeros rule a number out.
1. You must check whether the digits of an integer appear in non-decreasing order from left to right, without strings. Which approach fits best?
Popping from the right gives the digits in reverse order, so each new digit must be no larger than the one before. Reversing and comparing tests for a palindrome, and binary digits are a different number system.
2. Why does the shown code work on abs(x) instead of x?
-123 % 10 is 7 and -123 // 10 is −13, so the digits would be wrong and the loop would not end. Taking the absolute value first and restoring the sign later avoids this. Python does not raise an error here.
3. A learner removes sign and abs and loops on x directly. What happens for x = −123?
-1 // 10 is −1 in Python, so once x reaches −1 it never becomes 0 and the while x: loop runs forever. Positive inputs are unaffected.
Score 60% or more and the lesson is marked complete.