NUHMAN.com

Introduction

LeetCode 29: Divide Two Integers challenges you to implement integer division without using the division (/), multiplication (*), or modulo (%) operators.

This is a great problem to test your understanding of bitwise operations, edge case handling, and binary search-style logic.

Problem Statement

Given two integers dividend and divisor, divide two integers without using multiplication, division, and mod operator.

Constraints:

• Return the quotient after dividing dividend by divisor.
• The integer division should truncate toward zero.
• You must handle 32-bit signed integer overflow.

Examples

go

Input: dividend = 10, divisor = 3
Output: 3
go

Input: dividend = 7, divisor = -3
Output: -2
go

Input: dividend = -2147483648, divisor = -1
Output: 2147483647 // must clamp to avoid overflow

Approach: Bit Manipulation (Doubling Method)

We use subtraction and bit shifting to simulate division:

1. Repeatedly double the divisor (left shift) until it’s larger than the dividend.
2. Subtract the largest possible multiple and keep track of how many times you did that.
3. Handle negative signs and overflow.

Go Implementation

go

import "math"

func divide(dividend int, divisor int) int {
    // Handle overflow case
    if dividend == math.MinInt32 && divisor == -1 {
        return math.MaxInt32
    }

    // Determine the sign of the result
    negative := (dividend < 0) != (divisor < 0)

    // Convert to positive using int64 to prevent overflow
    a := int64(abs(dividend))
    b := int64(abs(divisor))
    result := int64(0)

    // Bitwise division logic
    for a >= b {
        temp := b
        multiple := int64(1)
        for a >= (temp << 1) {
            temp <<= 1
            multiple <<= 1
        }
        a -= temp
        result += multiple
    }

    if negative {
        result = -result
    }

    // Clamp result to 32-bit signed integer range
    if result > math.MaxInt32 {
        return math.MaxInt32
    }
    return int(result)
}

func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}

Explanation with Example

go

divide(10, 3):
- Start with a = 10, b = 3
- Double 3: 3 → 6 → 12 (stop at 6 because 12 > 10)
- Subtract 6 from 10, result += 2
- Remaining a = 4
- Double 3 again: 3 → okay, result += 1
- Final result = 3

Time and Space Complexity

MetricComplexityTime ComplexityO(log N)Space ComplexityO(1)

• Because we reduce the dividend by multiples of the divisor (doubling), we approach logarithmic time.

Key Edge Cases to Handle

• Overflow: dividend = -2³¹ and divisor = -1 → must clamp to 2³¹ - 1
• Negative signs: XOR logic to determine if result is negative
• Zero handling: Dividing zero returns zero

Key Takeaways

• This is a classic problem combining math + bit tricks.
• Use left-shifts to simulate fast subtraction.
• Always handle overflows and signs explicitly.