Reverse Integer
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 `[-2^31, 2^31 - 1]`, then return `0`. Assume the environment does not allow you to store 64-bit integers (signed or unsigned).
Examples
Constraints
-2^31 <= x <= 2^31 - 1
Math and Overflow Check
Approach
We can reverse the digits mathematically by repeatedly taking `x % 10` (to get the last digit) and dividing `x` by `10`. Before we append the extracted digit to our result `res` (by doing `res = res * 10 + digit`), we must check if doing so would cause an overflow. The max 32-bit integer is `2147483647` and the min is `-2147483648`. So, we check if `res > MAX / 10` (or `res == MAX / 10` and `digit > 7`). If so, we overflow. Similarly, we check if `res < MIN / 10` (or `res == MIN / 10` and `digit < -8`). If so, we overflow. Note: Python's modulo operator handles negative numbers differently than Java/C++, so we can use `math.fmod(x, 10)` to get the expected behavior, or handle the sign separately.
Complexity Analysis
Time complexity is O(log(x)) which corresponds to the number of digits in x (roughly log10(x)). Space complexity is O(1).
class Solution { public int reverse(int x) { int res = 0; while (x != 0) { int digit = x % 10; x /= 10; // Check for overflow before multiplying by 10 and adding digit if (res > Integer.MAX_VALUE / 10 || (res == Integer.MAX_VALUE / 10 && digit > 7)) { return 0; } if (res < Integer.MIN_VALUE / 10 || (res == Integer.MIN_VALUE / 10 && digit < -8)) { return 0; } res = (res * 10) + digit; } return res; }}