LeetCode 29 - Divide Two Integers

LeetCode Problem 29

Difficulty: 🟡 Medium
Topics: Math, Bit Manipulation

Solution

Problem Understanding

The problem asks us to implement integer division without using the standard arithmetic operators for multiplication, division, or modulo. We are given two integers, dividend and divisor, and we must compute the quotient obtained by dividing the dividend by the divisor.

The result must follow truncation toward zero. This means that any fractional portion is discarded instead of rounded. For example:

• 10 / 3 = 3.333..., truncated to 3
• 7 / -3 = -2.333..., truncated to -2

The problem also introduces an important constraint related to 32-bit signed integers. The valid range is:

$$[-2^{31}, 2^{31} - 1]$$

which corresponds to:

$$[-2147483648, 2147483647]$$

If the computed quotient exceeds this range, we must clamp the result:

• Larger than 2147483647 becomes 2147483647
• Smaller than -2147483648 becomes -2147483648

The constraints tell us several important things:

• The input size is constant, because integers are bounded to 32 bits.
• A naive repeated subtraction approach may still be too slow in the worst case.
• Overflow handling is critical, especially for:

$$-2^{31} \div -1$$

because the mathematical result would be:

$$2147483648$$

which is outside the 32-bit signed integer range.

Another subtle issue is handling negative numbers correctly. Integer division truncates toward zero, not toward negative infinity. Languages differ in how they treat negative division, so we must implement the logic carefully.

Important edge cases include:

• Dividing the smallest negative integer by -1
• Dividing by 1 or -1
• Very large positive or negative dividends
• Cases where the quotient is zero
• Negative dividend with positive divisor, and vice versa

The problem guarantees that divisor != 0, so division by zero never needs to be handled.

Approaches

Brute Force Approach

The most straightforward idea is repeated subtraction.

We repeatedly subtract the divisor from the dividend until the remaining value becomes smaller than the divisor. The number of successful subtractions is the quotient.

For example:

• 10 / 3
• 10 - 3 = 7
• 7 - 3 = 4
• 4 - 3 = 1
• We performed subtraction 3 times, so the answer is 3

This approach is correct because division fundamentally represents repeated subtraction.

However, this solution becomes extremely slow for large numbers. Consider:

$$2147483647 \div 1$$

This would require over two billion subtraction operations, which is far too slow.

Optimal Approach

The key insight is that repeated subtraction can be accelerated using doubling and bit shifting.

Instead of subtracting the divisor one time per iteration, we repeatedly double the divisor until it becomes as large as possible while still fitting inside the remaining dividend.

For example:

• divisor = 3

• doubled values:

• 3

• 6

• 12

• 24

• ...

This is similar to how binary long division works.

Bit shifting is useful because:

$$x << 1 = x \times 2$$

Doubling allows us to remove large chunks of the dividend at once, dramatically reducing the number of operations.

The runtime becomes logarithmic because each subtraction removes a power-of-two multiple of the divisor.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(dividend / divisor)	O(1)	Repeatedly subtracts divisor one step at a time
Optimal	O(log n)	O(1)	Uses exponential doubling and bit manipulation

Algorithm Walkthrough

Step 1: Handle Overflow Case

The only overflow scenario occurs when:

$$-2^{31} \div -1$$

because the result becomes:

$$2^{31}$$

which exceeds the maximum 32-bit signed integer.

We immediately return:

$$2^{31} - 1$$

for this case.

Step 2: Determine the Sign of the Result

The quotient is negative if exactly one of the inputs is negative.

We can determine this using XOR logic:

• positive / positive → positive
• negative / negative → positive
• positive / negative → negative
• negative / positive → negative

Step 3: Convert Both Numbers to Positive

Working with positive integers simplifies the logic.

We take absolute values of both the dividend and divisor.

Step 4: Repeatedly Find the Largest Double

While the remaining dividend is at least as large as the divisor:

1. Start with:

• current_divisor = divisor
• multiple = 1

2. Double both values while doubling still fits inside the dividend:

• current_divisor <<= 1
• multiple <<= 1

3. Subtract the largest doubled divisor from the dividend.
4. Add the corresponding multiple to the quotient.

This efficiently removes large portions of the dividend.

Step 5: Apply the Correct Sign

If the result should be negative, negate the quotient.

Step 6: Return the Final Result

The quotient is now correctly computed with truncation toward zero.

Why it works

At every iteration, the algorithm subtracts the largest possible power-of-two multiple of the divisor that does not exceed the remaining dividend.

This guarantees two things:

1. Progress is maximized each iteration, which keeps the runtime logarithmic.
2. The accumulated multiples exactly represent the quotient in binary form.

Because every subtraction corresponds to a valid multiple of the divisor, the final quotient is mathematically correct.

Python Solution

class Solution:
    def divide(self, dividend: int, divisor: int) -> int:
        INT_MIN = -(2 ** 31)
        INT_MAX = (2 ** 31) - 1

        # Handle overflow case
        if dividend == INT_MIN and divisor == -1:
            return INT_MAX

        # Determine sign of result
        negative = (dividend < 0) != (divisor < 0)

        # Work with positive values
        dividend = abs(dividend)
        divisor = abs(divisor)

        quotient = 0

        while dividend >= divisor:
            current_divisor = divisor
            multiple = 1

            # Double divisor until it exceeds dividend
            while dividend >= (current_divisor << 1):
                current_divisor <<= 1
                multiple <<= 1

            dividend -= current_divisor
            quotient += multiple

        return -quotient if negative else quotient

The implementation begins by defining the 32-bit integer bounds. The special overflow case is handled immediately because it cannot be represented within the allowed range.

Next, the code determines whether the final answer should be negative. The expression:

(dividend < 0) != (divisor < 0)

evaluates to True when exactly one value is negative.

Both values are then converted to positive numbers using abs(). This avoids complications with negative arithmetic during repeated subtraction.

The outer loop continues as long as the dividend remains large enough to subtract the divisor.

Inside the loop, the algorithm repeatedly doubles the divisor using left shifts. Each left shift multiplies the number by two.

For every doubling:

current_divisor <<= 1
multiple <<= 1

the algorithm tracks both:

• the doubled divisor
• how many times the original divisor is represented

Once the largest valid doubled divisor is found, it is subtracted from the dividend, and the matching multiple is added to the quotient.

Finally, the sign is applied before returning the result.

Go Solution

func divide(dividend int, divisor int) int {
	INT_MIN := -1 << 31
	INT_MAX := (1 << 31) - 1

	// Handle overflow case
	if dividend == INT_MIN && divisor == -1 {
		return INT_MAX
	}

	negative := (dividend < 0) != (divisor < 0)

	// Convert to positive
	a := dividend
	if a < 0 {
		a = -a
	}

	b := divisor
	if b < 0 {
		b = -b
	}

	quotient := 0

	for a >= b {
		currentDivisor := b
		multiple := 1

		for a >= (currentDivisor << 1) {
			currentDivisor <<= 1
			multiple <<= 1
		}

		a -= currentDivisor
		quotient += multiple
	}

	if negative {
		return -quotient
	}

	return quotient
}

The Go implementation follows the same overall strategy as the Python version.

One important difference is that Go does not provide a built-in abs() function for integers in the standard library without importing additional packages, so absolute values are computed manually.

The overflow handling is also explicit because Go integers can vary depending on architecture, but LeetCode evaluates this problem under 32-bit constraints.

Bit shifting works efficiently in Go and is a natural fit for this algorithm.

Worked Examples

Example 1

Input:

dividend = 10
divisor = 3

Initial state:

Variable	Value
dividend	10
divisor	3
quotient	0

First iteration:

Step	current_divisor	multiple
Start	3	1
Double	6	2
Stop	6	2

Subtract:

10 - 6 = 4

Update quotient:

0 + 2 = 2

Second iteration:

Step	current_divisor	multiple
Start	3	1
Stop	3	1

Subtract:

4 - 3 = 1

Update quotient:

2 + 1 = 3

Now:

1 < 3

Loop ends.

Final answer:

3

Example 2

Input:

dividend = 7
divisor = -3

Determine sign:

negative = True

Convert to positive:

Variable	Value
dividend	7
divisor	3

First iteration:

Step	current_divisor	multiple
Start	3	1
Double	6	2
Stop	6	2

Subtract:

7 - 6 = 1

Update quotient:

0 + 2 = 2

Apply negative sign:

-2

Final answer:

-2

Complexity Analysis

Measure	Complexity	Explanation
Time	O(log n)	Each iteration removes a large power-of-two chunk
Space	O(1)	Only a fixed number of variables are used

The time complexity is logarithmic because the divisor is repeatedly doubled, allowing the algorithm to skip many subtraction operations at once.

The nested loop does not make the complexity quadratic. Each doubling corresponds to a bit position, and the number of bits in a 32-bit integer is bounded.

The algorithm uses constant extra memory because it stores only a few integer variables regardless of input size.

Test Cases

solution = Solution()

assert solution.divide(10, 3) == 3          # basic positive division
assert solution.divide(7, -3) == -2         # truncation toward zero
assert solution.divide(-7, 3) == -2         # negative dividend
assert solution.divide(-7, -3) == 2         # both negative
assert solution.divide(0, 1) == 0           # zero dividend
assert solution.divide(1, 1) == 1           # identity division
assert solution.divide(1, -1) == -1         # negative result
assert solution.divide(-1, 1) == -1         # negative dividend
assert solution.divide(-1, -1) == 1         # both negative small values
assert solution.divide(2147483647, 1) == 2147483647   # max int
assert solution.divide(-2147483648, 1) == -2147483648 # min int
assert solution.divide(-2147483648, -1) == 2147483647 # overflow clamp
assert solution.divide(-2147483648, 2) == -1073741824 # large negative division
assert solution.divide(2147483647, 2) == 1073741823   # truncation
assert solution.divide(3, 5) == 0           # quotient smaller than 1
assert solution.divide(100, 10) == 10       # exact division
assert solution.divide(81, 9) == 9          # another exact division

Test	Why
10 / 3	Standard truncating division
7 / -3	Negative quotient handling
-7 / 3	Negative dividend
-7 / -3	Double negative produces positive
0 / 1	Zero dividend
1 / 1	Simplest valid division
1 / -1	Sign handling
-1 / 1	Negative input correctness
-1 / -1	Positive result from two negatives
2147483647 / 1	Maximum positive integer
-2147483648 / 1	Minimum negative integer
-2147483648 / -1	Overflow edge case
-2147483648 / 2	Large negative division
2147483647 / 2	Truncation behavior
3 / 5	Quotient becomes zero
100 / 10	Exact division
81 / 9	Another exact division

Edge Cases

Overflow When Dividing Minimum Integer by -1

The most important edge case is:

-2147483648 / -1

Mathematically, the answer is:

2147483648

However, this exceeds the maximum 32-bit signed integer value. Without explicit handling, some languages overflow and produce incorrect results.

The implementation detects this case before any calculations and immediately returns:

2147483647

which matches the problem requirements.

Quotient Equal to Zero

Cases like:

3 / 5

can be easy to mishandle in subtraction-based algorithms.

Since the dividend is smaller than the divisor from the beginning, the outer loop never executes. The quotient remains 0, which is the correct truncated result.

Negative Number Handling

Integer division involving negative numbers is tricky because truncation toward zero differs from floor division.

For example:

-7 / 3 = -2

not -3.

The implementation avoids language-specific division behavior entirely by:

1. Working only with positive values during computation
2. Applying the sign afterward

This guarantees correct truncation semantics across all cases.