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;
    }
}

Step 1: State

int reversed = 0;

• You need a place to store the flipped number as you process it digit by digit.

Step 2: Start Reading the Digits

while (x != 0) {

• You can’t flip the digits without reading them one by one, so this loop ensures you keep going until you’ve handled all the digits.

Step 3: Extract Last Digit

int digit = x % 10;

• Extract last digit of the number using the % operators. For example, if the number is 123, the last digit is 3.

• You do this because you need to work with the digit individually to flip their order.

Step 4: Shrink The Number

x =/ 10;

• After peeling off the last digit, you shrink the number by removing that digit. For example, if the number was 123, it becomes 12.
• Once you;ve extracted the last digit, it’s no longer need, so you remove it to focus on the remaining digits.

Step 5: Check for overflow

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;

• Computers have a limit for how big or small numbers can be. This check ensures the program doesn’t crash when reversing very large numbers.

Step 6: Add The Digit

reversed = reversed * 10 + digit;

• Place extracted digit onto the new flipped number, creating reverse number piece by piece.

Step 8: Return

return reversed;

• Once the flipping is done, the program needs to output the final result.

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.