Reverse the digits of a 32-bit integer. Pop the last digit, push it onto the result, and check for overflow before each push.
▼The problem
LeetCode 7 (Medium). Given a signed 32-bit integer x, return x with its digits reversed. If reversing x makes the value go outside the signed 32-bit range [-2³¹, 2³¹ - 1], return 0. Assume the environment can't store 64-bit integers.
Examples: 123 → 321, -123 → -321, 120 → 21, and 1534236469 → 0 (reversed it is 9646324351, more than 2147483647).
The solution
LIMIT = (2**31 - 1) // 10 # 214748364
def reverse(x):
sign = -1 if x < 0 else 1
x, rev = abs(x), 0
while x:
digit = x % 10
x //= 10
if rev > LIMIT or (rev == LIMIT and digit > 7):
return 0
rev = rev * 10 + digit
return sign * revTranscript
Reverse Integer. Given a signed thirty two bit integer x, reverse its digits. If the result overflows the thirty two bit range, return zero. And you can't store sixty four bit numbers.
One twenty three becomes three twenty one. Minus one twenty three becomes minus three twenty one. One twenty becomes twenty one. But one five three four two three six four six nine, reversed, is over nine billion. Too big, so zero.
The easy way: make x a string, reverse it, convert back, then check the range. But that reversed number needs a bigger type. In real thirty two bit math, it overflows before you check.
Instead, move one digit at a time. Pop the last digit with x mod ten, then divide x by ten. Push it: rev times ten, plus the digit. For negative x, use its absolute value and restore the sign at the end.
The danger is the push. First compare rev with the limit over ten. If rev is bigger, times ten would overflow, so return zero. If equal, the digit can't exceed seven.
In code: save the sign, take the absolute value, and while x is not zero, pop, check, and push. Return sign times rev.
Run one twenty three. Pop three: rev is three. Pop two: thirty two. Pop one: three twenty one. Now the big one. Nine, ninety six, and on, until rev passes nine hundred million. That's above the limit over ten, so return zero.
Each step removes a digit, and x has at most ten. So time is order log x, and space is order one.
Pop a digit, check the guard, push it on. That's Reverse Integer.