Reverse Integer
MedPrompt
Given a signed 32-bit integer x, return x with its digits reversed. If reversing x causes the value to go outside the signed 32-bit integer range [-231, 231 - 1], then return 0.
Assume the environment does not allow you to store 64-bit integers (signed or unsigned).
Example 1:
Input: x = 123
Output: 321Example 2:
Input: x = -123
Output: -321Example 3:
Input: x = 120
Output: 21
Constraints:
-231 <= x <= 231 - 1
Approaches
2 approaches with complexity analysis and trade-offs.
This approach converts the integer to a string, reverses the string, and then converts it back to an integer. It handles the sign separately and uses a try-catch block to detect overflow during the final conversion, which respects the constraint of not using 64-bit integers.
Algorithm
- Determine the sign of the input integer
x. If it's negative, store the sign and proceed with the absolute value ofx. - Convert the absolute value of
xto its string representation. - Create a new
StringBuilderfrom the string and use itsreverse()method to reverse the digits. - Convert the reversed
StringBuilderback to a string. - Use a
try-catchblock to parse the reversed string back into an integer usingInteger.parseInt(). - Inside the
tryblock, if the parsing is successful, multiply the result by the original sign and return it. - If a
NumberFormatExceptionis caught, it means the reversed number is too large to fit in a 32-bit integer. In this case, return0.
Walkthrough
The core idea is to leverage built-in string manipulation functions. First, we handle the sign. If the number x is negative, we note this and proceed with its absolute value. Then, we convert this positive number into a string. The StringBuilder class provides a convenient reverse() method, which we use to reverse the string of digits. Finally, we attempt to parse this reversed string back into an integer. The Integer.parseInt() method will throw a NumberFormatException if the string represents a value outside the [-2^31, 2^31 - 1] range. By wrapping this parsing operation in a try-catch block, we can gracefully handle the overflow case by returning 0 from the catch block. If parsing succeeds, we re-apply the original sign to the result.
class Solution { public int reverse(int x) { String s = String.valueOf(x); String reversedS; int sign = 1; if (x < 0) { sign = -1; s = s.substring(1); // Remove the '-' sign } reversedS = new StringBuilder(s).reverse().toString(); try { int result = Integer.parseInt(reversedS); return result * sign; } catch (NumberFormatException e) { // This exception is thrown if the reversed string represents a number // larger than Integer.MAX_VALUE. return 0; } }}Complexity
Time
O(log10(x))
Space
O(log10(x))
Trade-offs
Pros
Conceptually simple and easy to implement.
Leverages built-in string manipulation and parsing functions, making the code concise.
Cons
Less efficient due to the overhead of type conversions between integer and string.
Requires extra space proportional to the number of digits to store the string representation.
This is a more efficient approach that avoids string conversions. It mathematically 'pops' the last digit from the input number and 'pushes' it to the end of the result. The main challenge is to check for potential overflow before it actually occurs, as we are constrained from using 64-bit integers.
Algorithm
- Initialize a variable
reversedto0. This will store the reversed integer. - Loop as long as the input
xis not0. - In each iteration, extract the last digit of
xusing the modulo operator:pop = x % 10. - Before updating
reversed, check for potential overflow. - Check for positive overflow: if
reversed > Integer.MAX_VALUE / 10or (reversed == Integer.MAX_VALUE / 10andpop > 7), return0. - Check for negative overflow: if
reversed < Integer.MIN_VALUE / 10or (reversed == Integer.MIN_VALUE / 10andpop < -8), return0. - If no overflow is detected, 'push' the digit to the reversed number:
reversed = reversed * 10 + pop. - Remove the last digit from
xby integer division:x = x / 10. - After the loop finishes, return
reversed.
Walkthrough
This method iteratively builds the reversed integer. In each step of a loop, we extract the last digit of the input number x using the modulo operator (pop = x % 10). We then remove this digit from x using integer division (x /= 10). The crucial part is adding the popped digit to our reversed result. Before we perform the operation reversed = reversed * 10 + pop, we must check if this would cause an overflow.
An overflow would occur if reversed * 10 is already greater than the maximum possible value for an integer, or if it's equal and the new digit pushes it over the edge. Specifically:
Integer.MAX_VALUEis2,147,483,647. Ifreversedis already greater than214,748,364, multiplying by 10 will surely overflow. Ifreversedis exactly214,748,364, thepopmust not be greater than7.Integer.MIN_VALUEis-2,147,483,648. Ifreversedis already less than-214,748,364, multiplying by 10 will underflow. Ifreversedis exactly-214,748,364, thepopmust not be less than-8.
By performing these checks before the multiplication and addition, we can detect and handle overflow, returning 0 as required, without ever exceeding the 32-bit integer limits.
class Solution { public int reverse(int x) { int reversed = 0; while (x != 0) { int pop = x % 10; x /= 10; // Check for overflow before it happens // Integer.MAX_VALUE is 2147483647 if (reversed > Integer.MAX_VALUE / 10 || (reversed == Integer.MAX_VALUE / 10 && pop > 7)) { return 0; } // Integer.MIN_VALUE is -2147483648 if (reversed < Integer.MIN_VALUE / 10 || (reversed == Integer.MIN_VALUE / 10 && pop < -8)) { return 0; } reversed = reversed * 10 + pop; } return reversed; }}Complexity
Time
O(log10(x))
Space
O(1)
Trade-offs
Pros
Highly efficient with O(1) space complexity, as it only uses a fixed number of variables.
Avoids the overhead associated with string creation, conversion, and garbage collection.
Considered the canonical solution for this type of problem in interviews.
Cons
The logic for checking overflow is more complex and less intuitive than using a try-catch block.
Solutions
Solution
public class Solution { public int Reverse(int x) { int ans = 0; for (; x != 0; x /= 10) { if (ans < int.MinValue / 10 || ans > int.MaxValue / 10) { return 0; } ans = ans * 10 + x % 10; } return ans; }}class Solution {public int reverse(int x) { int ans = 0; for (; x != 0; x /= 10) { if (ans < Integer.MIN_VALUE / 10 || ans > Integer.MAX_VALUE / 10) { return 0; } ans = ans * 10 + x % 10; } return ans; }}/** * @param {number} x * @return {number} */ var reverse = function (x) { const mi = -(2 ** 31); const mx = 2 ** 31 - 1; let ans = 0; for (; x != 0; x = ~~(x / 10)) { if (ans < ~~(mi / 10) || ans > ~~(mx / 10)) { return 0; } ans = ans * 10 + (x % 10); } return ans;};class Solution {public: int reverse(int x) { int ans = 0; for (; x; x /= 10) { if (ans < INT_MIN / 10 || ans > INT_MAX / 10) { return 0; } ans = ans * 10 + x % 10; } return ans; }};class Solution: def reverse(self, x: int) -> int: ans = 0 mi, mx = - (2 ** 31), 2 ** 31 - 1 while x: if ans < mi // 10 + 1 or ans > mx // 10: return 0 y = x % 10 if x < 0 and y > 0: y -= 10 ans = ans * 10 + y x = (x - y) // 10 return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.