Reverse Integer
Understanding the Problem
We need to take an integer, reverse its digits, and return the result. The complication is overflow. The reversed number might not fit in a 32-bit signed integer, and if it does not, we return 0.
The constraint against 64-bit integers is what makes this problem more than a string exercise. Without that restriction, we could reverse the digits using a long, check if the result fits in 32 bits, and be done. The problem instead requires detecting overflow before it happens, using only 32-bit arithmetic.
Two properties of the input shape the solution. Negative numbers stay negative after reversal. Trailing zeros in the input (the 0 in 120) disappear when the number is reversed, because leading zeros are not represented in integers.
Key Constraints:
-2^31 <= x <= 2^31 - 1→ The input is a 32-bit signed integer, range [-2,147,483,648, 2,147,483,647]. The range is not symmetric: the minimum is one larger in magnitude than the maximum, soabs(Integer.MIN_VALUE)does not fit in anint.- No 64-bit integers → We cannot use
longin Java orint64in Go to sidestep overflow detection. We must check for overflow within 32-bit bounds.
Approach 1: String Reversal
Intuition
Convert the number to a string, reverse the string, and convert it back to an integer. This works, but it sidesteps the arithmetic and overflow logic the problem is built around, and it leans on string parsing to detect overflow rather than reasoning about it.
It serves as a baseline. We handle the sign separately, reverse the digit characters, then parse the result. Overflow detection comes from catching the exception that parsing throws (in Java, NumberFormatException) or comparing against the 32-bit bounds.
Algorithm
- Record whether the number is negative, then work with the absolute value.
- Convert the absolute value to a string.
- Reverse the string.
- Parse the reversed string back to an integer.
- If parsing would overflow 32-bit bounds, return 0.
- Restore the sign and return.
Example Walkthrough
Code
- Time Complexity: O(d) where d is the number of digits. Converting to a string, reversing it, and parsing back are all proportional to the number of digits. Since d is at most 10 for a 32-bit integer, this is effectively O(1).
- Space Complexity: O(d). We create a string of length d. Again, effectively O(1) for bounded input.
The next approach reverses the digits with arithmetic alone and detects overflow before it happens, using only 32-bit comparisons.
Approach 2: Mathematical Digit-by-Digit Reversal
Intuition
Extract digits one at a time from the right (using x % 10) and build the reversed number from the left (by multiplying the running result by 10 and adding the digit). This is the standard technique for digit manipulation.
The part that needs care is overflow detection. Before computing result = result * 10 + digit, we check whether that operation would exceed 32-bit bounds. If result > Integer.MAX_VALUE / 10, then multiplying by 10 overflows regardless of the digit. If result == Integer.MAX_VALUE / 10 (which is 214,748,364), the digit decides it: any digit above 7 pushes the value past 2,147,483,647. The same reasoning applies on the negative side with -8, since Integer.MIN_VALUE ends in -8.
The check happens before the multiplication, never after. Signed integer overflow is undefined behavior in C++ and wraps around in Java, so testing the value after it overflows is unreliable. Comparing result against MAX_VALUE / 10 (= 214,748,364) catches every overflowing case: if result already exceeds 214,748,364, then result * 10 alone exceeds 2,147,483,640, and adding a digit only makes it worse. When result equals 214,748,364, the product is exactly 2,147,483,640, leaving room only for digits up to 7 before crossing 2,147,483,647.
The sign is handled implicitly in most languages. The modulo operator keeps the sign of the dividend in Java, C++, C#, Go, Rust, and JavaScript, so (-123) % 10 is -3, not 3. Negative inputs build a negative result directly, with no separate sign tracking. Python's % follows the sign of the divisor instead ((-123) % 10 is 7), so the Python implementation below works with abs(x) and reapplies the sign at the end.
Algorithm
- Initialize
result = 0. - While
xis not zero: - Extract the last digit:
digit = x % 10. - Remove the last digit from x:
x = x / 10. - Check for overflow before updating result:
- If
result > MAX_VALUE / 10or (result == MAX_VALUE / 10anddigit > 7), return 0. - If
result < MIN_VALUE / 10or (result == MIN_VALUE / 10anddigit < -8), return 0. - Update result:
result = result * 10 + digit. - Return
result.
Example Walkthrough
Code
- Time Complexity: O(log x). We process each digit exactly once. A number x has floor(log10(x)) + 1 digits. For 32-bit integers this is at most 10 digits, so it's effectively O(1).
- Space Complexity: O(1). We use only a constant number of variables regardless of input size.