Divide Two Integers - Go Solution

LeetCode

— 1 min read

Solving the LeetCode "Divide Two Integers" Problem in Go

Difficulty: Medium | Tags: Math, Bit Manipulation

Introduction

Dividing two integers without using multiplication, division, or mod operators is a classic problem that tests understanding of bit manipulation and efficient arithmetic operations. This problem requires careful handling of edge cases, especially overflow scenarios.

Problem Analysis

The problem requires dividing two integers, `dividend` and `divisor`, without using multiplication, division, or mod operators. The result must truncate toward zero. Additionally, we must handle 32-bit signed integer overflow by clamping the result to the range `[−2³¹, 2³¹ − 1]`. For example, dividing 10 by 3 yields 3, while dividing 7 by -3 yields -2.

Solution Approach

The solution involves using bit manipulation to perform efficient subtraction. The key idea is to subtract the divisor from the dividend in powers of two, doubling the divisor each time to speed up the process. We handle negative numbers by converting both inputs to their absolute values and tracking the sign of the result separately.

Go Implementation


func divide(dividend int, divisor int) int {
    // Handle overflow case
    if dividend == -1<<31 && divisor == -1 {
        return 1<<31 - 1
    }
    // Determine the sign of the result
    negative := (dividend < 0) != (divisor < 0)
    // Work with absolute values
    absDividend := abs(dividend)
    absDivisor := abs(divisor)
    quotient := 0
    for absDividend >= absDivisor {
        tempDivisor := absDivisor
        multiple := 1
        for absDividend >= (tempDivisor << 1) {
            if tempDivisor << 1 <= 0 { // Prevent overflow
            break
        }
        tempDivisor <<= 1
        multiple <<= 1
    }
    absDividend -= tempDivisor
    quotient += multiple
}
if negative {
    quotient = -quotient
}
// Clamp the result to 32-bit signed integer range
if quotient < -1<<31 {
    return -1<<31
} else if quotient > 1<<31-1 {
    return 1<<31-1
}
return quotient
}
func abs(x int) int {
if x < 0 {
    return -x
}
return x
}

Complexity Analysis

The time complexity of this solution is O(log n), where n is the absolute value of the dividend. This is because we double the divisor (or its multiple) in each iteration, reducing the problem size logarithmically. The space complexity is O(1), as we use a constant amount of additional space.

Testing and Examples

Key test cases include: - `dividend = 10, divisor = 3` → `3` - `dividend = 7, divisor = -3` → `-2` - `dividend = -2147483648, divisor = -1` → `2147483647` (overflow case) - `dividend = -2147483648, divisor = 1` → `-2147483648` (edge case)

Best Practices and Tips

Always handle overflow cases first, especially when dealing with 32-bit integers. Use bit shifting for efficient multiplication and division by powers of two. Track the sign of the result separately to simplify calculations. Test edge cases thoroughly, including minimum and maximum 32-bit integer values.

Read more