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 x. Store the sign (positive or negative) separately. We'll work with the absolute value of x to simplify the reversal process.

2. Reverse the digits: Reverse the digits of the absolute value of x. We can do this using a while loop and repeatedly popping the last digit using the modulo operator (%) and building the reversed number.

3. Check for overflow: Before returning the reversed number, check if it falls within the 32-bit signed integer range.

4. Apply the sign: Multiply the reversed number by the stored sign to get the final result.

Explanation

The core idea is to extract digits one by one from the input number and build the reversed number. The modulo operator (%) helps extract the last digit, and integer division (/) removes the last digit. We carefully handle potential overflow by checking the result against the boundaries of the 32-bit integer range.

Code

class Solution {
public:
    int reverse(int x) {
        long long rev = 0; // Use long long to handle potential overflow during intermediate calculations
        int sign = 1;

        if (x < 0) {
            sign = -1;
            x = -x; // Work with the absolute value
        }

        while (x > 0) {
            int pop = x % 10;
            x /= 10;
            rev = rev * 10 + pop;

            // Check for overflow before adding the next digit
            if (rev > INT_MAX || rev < INT_MIN) {
                return 0; 
            }
        }

        return (int)(rev * sign); 
    }
};

Complexity

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