Solving the LeetCode "Reverse Integer" Problem in Go

Difficulty: Medium | Tags: Math

Introduction

Reversing an integer is a common programming challenge that tests your ability to handle edge cases, such as overflow and negative numbers. This problem requires reversing the digits of a 32-bit signed integer while ensuring the result remains within the valid range.

Problem Analysis

The problem requires reversing the digits of a given 32-bit signed integer. If the reversed integer exceeds the 32-bit signed integer range (i.e., [-2³¹, 2³¹ - 1]), we must return 0. For example, reversing 123 gives 321, while reversing -123 gives -321. The challenge lies in handling overflow and negative numbers efficiently.

Solution Approach

To solve this problem, we can repeatedly extract the last digit of the input number and build the reversed number digit by digit. We must check for overflow at each step to ensure the reversed number remains within the 32-bit range. The steps are as follows:

1. Initialize a variable to store the reversed number.
2. While the input number is not zero:
   • Extract the last digit using modulo 10.
   • Update the reversed number by multiplying it by 10 and adding the extracted digit.
   • Check for overflow before updating the reversed number.
   • Remove the last digit from the input number using integer division by 10.
3. Return the reversed number or 0 if overflow occurs.

Go Implementation

func reverse(x int) int {
    const (
    maxInt32 = 1<<31 - 1
    minInt32 = -1 << 31
    )
    reversed := 0
    for x != 0 {
        digit := x % 10
        x /= 10
        // Check for overflow before updating reversed
        if reversed > maxInt32/10 || (reversed == maxInt32/10 && digit > 7) {
            return 0
        }
        if reversed < minInt32/10 || (reversed == minInt32/10 && digit < -8) {
            return 0
        }
        reversed = reversed*10 + digit
    }
    return reversed
}

Complexity Analysis

The time complexity of this solution is O(log₁₀(x)), as we process each digit of the input number once. The space complexity is O(1), as we use a constant amount of additional space regardless of the input size.

Testing and Examples

Here are some test cases to validate the solution:

• Input: 123 → Output: 321
• Input: -123 → Output: -321
• Input: 120 → Output: 21
• Input: 1534236469 → Output: 0 (overflow)
• Input: -2147483648 → Output: 0 (overflow)

Best Practices and Tips

Key takeaways for solving this problem include:

• Always handle negative numbers by preserving the sign during reversal.
• Check for overflow at each step to avoid incorrect results.
• Use mathematical operations (modulo and division) to extract and process digits efficiently.
• Test edge cases, such as the minimum and maximum 32-bit integer values, to ensure robustness.