LeetCode 29: Divide Two Integers

Problem Restatement

We are given two integers, dividend and divisor.

We need to compute the integer quotient of:

dividend / divisor

But we cannot use multiplication, division, or modulo operators.

The result should truncate toward zero. That means we remove the fractional part.

Examples:

10 / 3 = 3.333...  -> 3
7 / -3 = -2.333... -> -2

The answer must stay inside the 32-bit signed integer range:

[-2^31, 2^31 - 1]

If the answer is larger than 2^31 - 1, return 2^31 - 1.

The divisor is never zero. The statement gives -2^31 <= dividend, divisor <= 2^31 - 1 and divisor != 0.

Input and Output

Function shape:

def divide(dividend: int, divisor: int) -> int:
    ...

Examples

Example 1:

dividend = 10
divisor = 3

The exact value is:

10 / 3 = 3.333...

After truncating toward zero:

3

Return:

3

Example 2:

dividend = 7
divisor = -3

The exact value is:

7 / -3 = -2.333...

After truncating toward zero:

-2

Return:

-2

Example 3:

dividend = -2147483648
divisor = -1

The exact value is:

2147483648

This is greater than the maximum 32-bit signed integer.

Return:

2147483647

First Thought: Repeated Subtraction

Division can be seen as repeated subtraction.

For example:

10 / 3

means:

10 - 3 = 7
7 - 3 = 4
4 - 3 = 1

We subtracted 3 exactly 3 times.

So the quotient is 3.

A direct version would look like this:

class Solution:
    def divide(self, dividend: int, divisor: int) -> int:
        negative = (dividend < 0) != (divisor < 0)

        a = abs(dividend)
        b = abs(divisor)

        quotient = 0

        while a >= b:
            a -= b
            quotient += 1

        if negative:
            quotient = -quotient

        return quotient

This gives the right idea, but it is too slow.

Problem With Repeated Subtraction

If dividend is very large and divisor is small, repeated subtraction needs too many loops.

For example:

2147483647 / 1

The loop would subtract 1 more than two billion times.

That is not practical.

We need to subtract larger chunks.

Key Insight

Instead of subtracting one divisor at a time, subtract doubled groups.

For example, to compute:

43 / 3

The divisor can be doubled:

The largest doubled value that fits inside 43 is 24, which equals 8 copies of 3.

Subtract it:

43 - 24 = 19

Now repeat with 19.

The largest doubled value that fits is 12, which equals 4 copies.

19 - 12 = 7

Now the largest doubled value that fits is 6, which equals 2 copies.

7 - 6 = 1

Now 1 < 3, so we stop.

The quotient is:

8 + 4 + 2 = 14

And:

43 / 3 = 14 remainder 1

This avoids subtracting 3 fourteen times.

Algorithm

First handle the overflow case:

if dividend == -2**31 and divisor == -1:
    return 2**31 - 1

Then determine the sign of the answer.

The answer is negative when exactly one of dividend and divisor is negative.

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

Work with positive absolute values:

a = abs(dividend)
b = abs(divisor)

Now compute how many times b fits into a.

While a >= b:

1. Start with one copy of b.
2. Keep doubling the current chunk while the doubled chunk still fits inside a.
3. Subtract the largest chunk from a.
4. Add the corresponding count to the quotient.

At the end, apply the sign.

Correctness

The algorithm keeps a remaining value a.

At any point, the original absolute dividend equals:

quotient * abs(divisor) + a

The algorithm repeatedly chooses a doubled chunk:

abs(divisor), 2 * abs(divisor), 4 * abs(divisor), ...

Each chunk is a valid multiple of the divisor, and the chosen chunk never exceeds the current remaining value a.

When we subtract a chunk, we add its multiple count to quotient. Therefore, the invariant remains true.

The loop stops when:

a < abs(divisor)

At that point, the remaining value is smaller than one more divisor, so no additional whole copy of the divisor can fit.

Thus quotient is exactly the integer quotient of the absolute values.

Finally, applying the sign gives truncation toward zero. The overflow case is handled before the main loop, so the returned value respects the 32-bit signed integer range.

Complexity

Here, n = abs(dividend).

For 32-bit integers, this is fast because there are only about 31 useful bit positions.

Implementation

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

        if dividend == INT_MIN and divisor == -1:
            return INT_MAX

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

        a = abs(dividend)
        b = abs(divisor)

        quotient = 0

        while a >= b:
            current = b
            count = 1

            while (current << 1) <= a:
                current <<= 1
                count <<= 1

            a -= current
            quotient += count

        if negative:
            quotient = -quotient

        return quotient

Code Explanation

We define the 32-bit bounds:

INT_MIN = -2**31
INT_MAX = 2**31 - 1

The only overflow case is:

-2147483648 / -1 = 2147483648

That value is too large for a signed 32-bit integer, so we return INT_MAX.

if dividend == INT_MIN and divisor == -1:
    return INT_MAX

Next, compute the result sign:

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

This is true when one number is negative and the other is positive.

Then use absolute values:

a = abs(dividend)
b = abs(divisor)

The main loop runs while another copy of the divisor can still fit:

while a >= b:

For each round, start with one copy:

current = b
count = 1

Then double both the chunk value and the count while the doubled chunk still fits:

while (current << 1) <= a:
    current <<= 1
    count <<= 1

The shift current << 1 means doubling current.

After finding the largest valid chunk, subtract it:

a -= current

Then add its count to the quotient:

quotient += count

Finally, apply the sign:

if negative:
    quotient = -quotient

Return the quotient.

Testing

def check(dividend: int, divisor: int, expected: int) -> None:
    actual = Solution().divide(dividend, divisor)
    assert actual == expected, (dividend, divisor, actual, expected)

def run_tests():
    check(10, 3, 3)
    check(7, -3, -2)
    check(0, 1, 0)
    check(1, 1, 1)
    check(-10, 3, -3)
    check(10, -3, -3)
    check(-10, -3, 3)
    check(43, 3, 14)
    check(-2147483648, -1, 2147483647)
    check(-2147483648, 1, -2147483648)
    check(-2147483648, 2, -1073741824)
    check(2147483647, 1, 2147483647)

    print("all tests passed")

run_tests()

Test meaning: