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

Steps

1. Handle the sign: Determine the sign of the input integer. Store the sign in a variable (e.g., sign). Take the absolute value of the input to simplify the reversal process.

2. Reverse the digits: Use a while loop to iteratively extract the last digit using the modulo operator (%). Build the reversed integer by multiplying the current reversed integer by 10 and adding the extracted digit.

3. Check for overflow: Before adding the next digit, check if the intermediate result exceeds the maximum or minimum value of a 32-bit integer. If it does, return 0 to indicate overflow.

4. Apply the sign: After the reversal, multiply the reversed integer by the stored sign to restore the original sign.

5. Return the result: Return the final reversed integer.

Explanation

The algorithm efficiently reverses the digits of an integer while handling potential overflow issues. The use of the modulo operator (%) allows for easy extraction of the last digit, and the multiplication by 10 effectively shifts existing digits to the left to accommodate the new digit. The overflow check prevents unexpected behavior and ensures the result is within the allowed range.

Code

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

        long rev = 0; // Use long to handle potential overflow during intermediate calculations
        while (x > 0) {
            int pop = x % 10;
            x /= 10;

            // Check for overflow before adding the next digit
            if (rev > int.MaxValue / 10 || (rev == int.MaxValue / 10 && pop > 7)) {
                return 0;
            }
            if (rev < int.MinValue / 10 || (rev == int.MinValue / 10 && pop < -8)) {
                return 0;
            }

            rev = rev * 10 + pop;
        }

        return (int)(rev * sign); // Cast back to int and apply the sign
    }
}

Complexity

• Time Complexity: O(log₁₀(n)), where n is the input integer. The number of iterations in the while loop is proportional to the number of digits in the integer. The logarithm base 10 reflects the fact that we're dealing with decimal digits.

• Space Complexity: O(1). The algorithm uses a constant amount of extra space, regardless of the input size. We only store a few variables.