Reverse Integer – 7. LeetCode

The Reverse Integer problem asks us to take an integer as input and return its digits reversed. For example, if the input is 123, the output should be 321. If the input is negative, like -123, the output should be -321. There is a constraint: if reversing the integer causes it to exceed the 32-bit signed integer range ([-2^31, 2^31 – 1]), you should return 0.

Simple Analogy: Imagine flipping the digits of a number as if you were flipping a card with digits on it to read it backward. If the number becomes too large or too small for a machine to handle, you discard it.

Brute Force Approach

public class ReverseIntegerBruteForce {
    public int reverse(int x) {
        boolean isNegative = x < 0;
        x = Math.abs(x);
        String reversedString = new StringBuilder(String.valueOf(x)).reverse().toString();
        try {
            int reversed = Integer.parseInt(reversedString);
            return isNegative ? -reversed : reversed;
        } catch (NumberFormatException e) {
            return 0; // Overflow case
        }
    }
}

Explanation:

1. Check if the number is negative.

2. Convert the absolute value of the integer into a string, reverse it, and parse it back to an integer.

3. If parsing causes an overflow, return 0.

Limitations:

• This approach uses string manipulation, which is unnecessary for a numerical problem.

• It involves higher space complexity due to the string operations.

Optimal Approach

Algorithm and Data Structure

Chosen Algorithm: Mathematical digit extraction.

Instead of converting the number to a string, we can reverse the integer mathematically by extracting its digits using modulus and division operations:

• Repeatedly extract the last digit of the number using x % 10.

• Append this digit to the reversed number by multiplying the reversed number by 10 and adding the extracted digit.

• Divide the number by 10 to process the next digit.

• Handle overflow by checking whether the reversed number would exceed the 32-bit integer range before performing the multiplication or addition.

Steps of the Algorithm

1. Initialize reversed to 0.

2. While x is not 0:

• Extract the last digit using x % 10.

• Check if adding this digit would cause an overflow.

• Append the digit to reversed by multiplying reversed by 10 and adding the digit.

• Remove the last digit from x using x / 10.

3. Return the reversed integer or 0 if an overflow occurs.

public class ReverseInteger {
    public int reverse(int x) {
        int reversed = 0;
        while (x != 0) {
            int digit = x % 10; // Extract the last digit
            x /= 10; // Remove the last digit
            
            // Check for overflow before updating `reversed`
            if (reversed > Integer.MAX_VALUE / 10 || 
                (reversed == Integer.MAX_VALUE / 10 && digit > 7)) return 0;
            if (reversed < Integer.MIN_VALUE / 10 || 
                (reversed == Integer.MIN_VALUE / 10 && digit < -8)) return 0;

            reversed = reversed * 10 + digit; // Append the digit
        }
        return reversed;
    }
}

Line By Line Explanation

Step 1: Initialize reversed Variable

int reversed = 0;

• Initialize variables clearly outside of loops for better readability.

Step 2: Start a Loop to Process All Digits

while (x != 0) {

• The condition x != 0 ensures the loop stops once all digits have been processed, maintaining clarity.

Step 3: Extract the Last Digit

int digit = x % 10;
x /= 10;

• Extracting digits allows us to build number digit by digit.
• Removing the last digit ensures progress toward termination of the loop.
• Avoids unnecessary string conversions or data structures for processing digits.

Step 4: Check for Overflow or Underflow

if (reversed > Integer.MAX_VALUE / 10 || 
    (reversed == Integer.MAX_VALUE / 10 && digit > 7)) return 0;
if (reversed < Integer.MIN_VALUE / 10 || 
    (reversed == Integer.MIN_VALUE / 10 && digit < -8)) return 0;

• Explicitly handling overflow/underflow is critical in competitive programming to meet edge case requirements.

• Mathematical checks avoid slower Java exceptions and ensure efficient operation.

Step 5: Append the Digit to reversed

reversed = reversed * 10 + digit;

• This operation builds the reversed number incrementally. By multiplying reversed by 10, we make room for the next digit, and then we add the next digit.

Step 6: Return

return reversed;

• Returns the fully reversed number stored in reversed.

Why This Algorithm is Better

• Avoids unnecessary data structure overhead (e.g., strings in the brute force approach).

• Operates in constant space, ensuring efficiency for large inputs.

• Directly processes digits, aligning with low-level computational patterns.

This approach demonstrates a fundamental understanding of numerical operations, leveraging simplicity and efficiency over brute force techniques.