Reverse Integer medium

Problem Statement

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³¹, 2³¹ - 1], then return 0.

Example 1

Input: x = 123 Output: 321

Example 2

Input: x = -123 Output: -321

Example 3

Input: x = 120 Output: 21

Steps

1. Handle the sign: Determine the sign of the input integer x. Store the sign (1 or -1) separately and work with the absolute value of x.
2. Reverse the digits: Use a while loop to iteratively extract digits from the rightmost position. Build the reversed integer using modular arithmetic (% 10) and integer division (/ 10).
3. Check for overflow: Before adding each digit to the reversed integer, check if adding it would cause an overflow. We can do this by comparing (reversed - Integer.MIN_VALUE) / 10 with (x % 10). If the result is less than 0 after division, it indicates an overflow.
4. Apply the sign: After reversing the digits, multiply the reversed integer by the stored sign to restore the original sign.
5. Return the result: Return the reversed integer if no overflow occurred; otherwise, return 0.

Explanation

The core idea is to extract digits one by one from the input integer and build the reversed integer. Modular arithmetic (% 10) gets the last digit, and integer division (/ 10) removes the last digit. The overflow check is crucial to ensure that the reversed integer remains within the 32-bit integer range. We avoid using Long to prevent implicit type conversion and potential overflow issues.

Code

class Solution {
    public int reverse(int x) {
        int sign = 1;
        if (x < 0) {
            sign = -1;
            x = -x; // Make x positive for easier processing
        }

        int reversed = 0;
        while (x > 0) {
            int lastDigit = x % 10;
            if ((reversed - Integer.MIN_VALUE) / 10 < lastDigit) { //Overflow check
                return 0;
            }
            reversed = reversed * 10 + lastDigit;
            x /= 10;
        }

        return reversed * sign;
    }
}

Complexity

• Time Complexity: O(log₁₀(n)), where n is the absolute value of the input integer. The number of iterations in the while loop is proportional to the number of digits in the integer.
• Space Complexity: O(1). The algorithm uses a constant amount of extra space.