7. Reverse Integer

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

1. 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.
2. 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.
3. 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.
4. 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
    }
};