
Description
The problem requires reversing the digits of a given 32-bit signed integer. However, the reversed integer must still fit within the 32-bit signed integer range. If it exceeds this range, the function should return 0. Additionally, negative numbers should retain their sign after reversal.
Intuition
The key insight is that reversing the digits of an integer can be done by repeatedly extracting the last digit and building a new number in reverse order. Care must be taken to handle negative numbers, and it's crucial to check for overflow after the reversal process.
Approach
- Sign Handling: Determine if the number is negative and work with its absolute value. The sign will be reapplied to the result at the end.
- Reversing the Digits: Use a loop to extract each digit (by taking the remainder when divided by 10), and build the reversed number by shifting the previous digits and adding the new one.
- Overflow Check: After reversing, verify if the resulting number fits within the limits of a 32-bit signed integer. If it doesn't, return 0.
- Return the Result: Multiply the reversed number by the sign and return it as the final output.
Complexity
Time Complexity:
O(logāā(x)), where x
is the input number. This is because the number of digits in x
determines the number of iterations needed.
Space Complexity:
O(1), as the algorithm uses a constant amount of space, regardless of the input size.
Code
C++
class Solution {
public:
int reverse(int x) {
int sign = (x < 0) ? -1 : 1; // Determine the sign of x
x = abs(x); // Work with the absolute value of x
long reversedNumber = 0; // Use long to handle potential overflow
while (x != 0) {
int digit = x % 10; // Get the last digit
reversedNumber = reversedNumber * 10 + digit; // Build the reversed number
x /= 10; // Remove the last digit
}
// Check for overflow (must fit within a 32-bit signed integer)
if (reversedNumber > INT_MAX) {
return 0;
}
return sign * (int)reversedNumber; // Restore the sign and return
}
};
Python
class Solution:
def reverse(self, x: int) -> int:
mod = 2**31 # Modulo for overflow checking
sign = -1 if x < 0 else 1
x *= sign
reversed_number = int(str(x)[::-1])
# Check for overflow
if reversed_number > mod - 1:
return 0
return sign * reversed_number
Java
class Solution {
public int reverse(int x) {
long reversedNumber = 0;
while (x != 0) {
int digit = x % 10;
reversedNumber = reversedNumber * 10 + digit;
x /= 10;
}
// Check for overflow
if (reversedNumber > Integer.MAX_VALUE || reversedNumber < Integer.MIN_VALUE) {
return 0;
}
return (int)reversedNumber;
}
}
JavaScript
var reverse = function (x) {
if (x === 0) return 0
const mod = 2 ^ 31
const str = x.toString().split('')
let l = 0, r = str.length - 1;
while (str[0] === '0') l++
while (str[r] === '0') r--
let str1 = str.slice(l, r + 1)
if (str1[0] === '-') str1.shift()
const n = Number(str1.reverse().join(''));
if (n > Math.pow(2, 31) - 1) return 0
else if (x < 0) {
str.pop()
return -1 * n
} else {
return n
}
};