Reverse Integer | Leetcode 7 Solution

Introduction

The Reverse Integer problem is a classic LeetCode challenge, categorized as an Easy level problem, but it’s a great exercise in understanding integer manipulation and overflow handling. This problem is frequently asked in coding interviews, making it a must-practice for aspiring developers. In this blog post, we’ll break down the problem, explore different solution approaches, and implement the solution in Java.

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], return 0.

Example 1

Input: x = 123
Output: 321

Example 2

Input: x = -123
Output: -321

Example 3

Input: x = 120
Output: 21

Constraints

1. The input is a 32-bit signed integer.
2. Reversed integer should not overflow beyond the 32-bit range.

Key Concepts

The problem revolves around manipulating digits of an integer and handling edge cases involving negative numbers and overflow scenarios.

Step-by-Step Solution Approach

Step 1: Isolate Digits

To reverse an integer, the first step is to extract its digits. Use the modulo (%) and division (/) operators:

• x % 10 gives the last digit.
• x / 10 removes the last digit from x.

Step 2: Construct the Reversed Integer

Iteratively build the reversed integer by multiplying the current reversed number by 10 and adding the next extracted digit:

• Initialize reversed = 0.
• In each iteration:
  reversed = reversed * 10 + lastDigit.

Step 3: Handle Overflow

Since we’re dealing with a 32-bit integer, it’s crucial to check if the reversed integer might overflow:

• The range of a signed 32-bit integer is [-2³¹, 2³¹ - 1] ([-2147483648, 2147483647]).
• If reversing an integer causes it to exceed this range, return 0.

Java Code Implementation

Here’s the Java solution, step-by-step:

public class ReverseInteger {

    public int reverse(int x) {
        int reversed = 0;

        while (x != 0) {
            int digit = x % 10;
            x /= 10;
            
            // Check for overflow
            if (reversed > Integer.MAX_VALUE / 10 || (reversed == Integer.MAX_VALUE / 10 && digit > 7)) {
                return 0; // Overflow case
            }
            if (reversed < Integer.MIN_VALUE / 10 || (reversed == Integer.MIN_VALUE / 10 && digit < -8)) {
                return 0; // Underflow case
            }

            // Add the digit to the reversed number
            reversed = reversed * 10 + digit;
        }

        return reversed;
    }
    
    public static void main(String[] args) {
        ReverseInteger solution = new ReverseInteger();
        System.out.println("Reversed 123: " + solution.reverse(123));   // Output: 321
        System.out.println("Reversed -123: " + solution.reverse(-123)); // Output: -321
        System.out.println("Reversed 120: " + solution.reverse(120));   // Output: 21
        System.out.println("Reversed 1534236469: " + solution.reverse(1534236469)); // Output: 0 (Overflow)
    }
}

Explanation

1. The method reverse(int x) initializes the reversed variable to 0.
2. A while loop runs until x becomes 0, extracting digits and constructing the reversed number.
3. Overflow is checked using conditions:
   • If reversed is about to exceed Integer.MAX_VALUE or go below Integer.MIN_VALUE, the function returns 0.
4. If no overflow is detected, the digits are appended, and the process continues until x is fully reversed.

Complexity Analysis

1. Time Complexity: O(log₁₀(n)) – The algorithm processes each digit once, and the number of digits in an integer n is log₁₀(n).
2. Space Complexity: O(1) – We use only a constant amount of extra space.

Edge Cases

1. Zero Ending: Reversing a number with trailing zeros (e.g., 120) should not retain zeros. Result should be 21.
2. Negative Numbers: Negative numbers should maintain their sign (e.g., -123 becomes -321).
3. Overflow: Input like 1534236469 will reverse to a number that exceeds 32-bit, hence returning 0.

Tips for Beginners

• Always consider edge cases when solving problems involving integer manipulation, especially for overflow.
• Use the Integer.MAX_VALUE and Integer.MIN_VALUE constants for comparison to handle potential overflow.

Conclusion

The Reverse Integer problem is simple yet full of hidden complexities, making it an excellent challenge to refine your problem-solving skills. It requires a solid understanding of integer operations and overflow handling. Practice the problem on platforms like LeetCode to sharpen your skills, and try implementing the solution in different languages!

By mastering such problems, you’ll gain confidence for interviews and other competitive coding challenges. Good luck!