The problem
Reverse the digits of a signed 32-bit integer x: 123 becomes 321, −123 becomes −321, 120 becomes 21. If the result falls outside the 32-bit range, from −2³¹ to 2³¹ − 1, return 0.
Assume the machine cannot store 64-bit integers, so the overflow must be caught before it happens.
Examples
- Input
x = 123
- Output
321
- Input
x = -123
- Output
-321
- Input
x = 120
- Output
21
Constraints
- −2³¹ ≤ x ≤ 2³¹ − 1
The idea
Pop digits off the end of x with % 10 and / 10, and push them onto the answer with out × 10 + d.
The only danger is that last push. The 32-bit limit is 2,147,483,647, so before pushing, check: if out is already more than 214,748,364, times ten is too big; if it equals 214,748,364, the new digit may be at most 7. The negative side is the same with −214,748,364 and −8. Checking first means the overflow never happens.
- Time
- O(log x) — one step per digit
- Space
- O(1)
Solution · every language run against every case
class Solution: def reverse(self, x: int) -> int: LIMIT = 2**31 - 1 sign = -1 if x < 0 else 1 x, out = abs(x), 0 while x: x, d = divmod(x, 10) # Check before growing: out * 10 + d must stay within 32 bits. if out > (LIMIT - d) // 10: return 0 out = out * 10 + d return sign * out