29. Divide Two Integers

Problem¶

Compute integer division of dividend / divisor without using *, /, or %, truncating toward zero and clamping to 32-bit signed range.

Example:

input:  dividend = 7, divisor = -3
output: -2
why:    7 / -3 = -2.333..., truncate toward 0 -> -2

Key trick¶

Use binary long division:

Work with absolute values.
From the largest bit down to 0, check whether divisor << shift fits into the remaining dividend.
If it fits, subtract it and set that bit in the quotient.
Apply the sign at the end.
Handle the single overflow case: INT_MIN / -1.

Trap¶

Common mistakes:

Using repeated subtraction, which is $O(|q|)$ and too slow.
Forgetting truncation is toward zero, not floor.
Missing the overflow case -2^31 / -1.
Mishandling signs before/after absolute values.

Why is it interesting?¶

It tests whether you can turn arithmetic into bit manipulation:

convert division into repeated doubling,
reason about overflow carefully,
and write an $O(32)$ solution instead of a brute-force one.

Python solution¶

class Solution:
    def divide(self, dividend: int, divisor: int) -> int:
        a, b = dividend, divisor

        # 32-bit signed integer bounds
        INT_MIN = -(1 << 31)
        INT_MAX = (1 << 31) - 1

        # Only overflowing case in 32-bit signed division
        if a == INT_MIN and b == -1:
            return INT_MAX

        negative = (a < 0) != (b < 0)
        a = abs(dividend)
        b = abs(divisor)

        quotient = 0

        # Try to place each bit of the quotient from high to low
        for shift in range(31, -1, -1):
            if (b << shift) <= a:
                a -= b << shift
                quotient |= 1 << shift

        return -quotient if negative else quotient

Comment on my solution¶

Your solution has the right high-level idea first, but the implementation has major issues:

It uses repeated subtraction, so worst-case time is $O(|\text{quotient}|)$, which times out for large inputs like (2147483647, 1).
The INT_MIN handling is incorrect.
- -2147483648 / -1 should return 2147483647, not -2147483648.
- abs(INT_MIN) is not a problem in Python, because Python integers are unbounded.
The overflow checks inside the loop are unnecessary in Python and still do not fix performance.
The accepted approach is to subtract large shifted multiples of the divisor, not one divisor at a time.

## Solution

# Time Limit Exceeded - 11 / 994 testcases passed
# Solution().divide(2147483647, 1)
class Solution:
    def divide(self, dividend: int, divisor: int) -> int:
        # - we could use successive substraction and count iterations loop
        #   - dividend -= divisor
        # - 8 / 3 = 2.6... => divide(8,3) = 2
        #   8 - 3 = 5
        #   5 - 3 = 2
        #   - so we iterate while dividend >= divisor
        # - because of 32-bit constraint we must check count a each step
        #   - when quotient > 2^31 - 1 with dividend = quotient * divisor + remaining
        #         quotient > 2^31 - 1
        #     <=> (dividend - remaining) / divisor > 2^32 - 1
        #     <=> dividend > divisor * (2^32 - 1) + remaining
        #   - if quotient > 2^32 - 1
        #     => quotient * divisor > 2^32 - 1

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

        quotient = 0
        dividend_sign = -1 if dividend < 0 else 1
        divisor_sign = -1 if divisor < 0 else 1
        sign = dividend_sign * divisor_sign

        # We can't the abs() of INT_MIN which will be out-of-bound
        if dividend == INT_MIN:
            if sign == -1:
                return INT_MIN
            else:
                return INT_MAX

        dividend = abs(dividend)
        divisor = abs(divisor)

        while dividend >= divisor:
            if sign == 1 and quotient == INT_MAX:
                return INT_MAX
            if sign == -1 and quotient == -INT_MIN:
                return INT_MIN
            quotient += 1
            dividend -= divisor
        return sign * quotient

Solution().divide(10, 3) # 3
Solution().divide(8, 3)  # 2
Solution().divide(-7, 3) # -2
Solution().divide(7, -3) # -2
Solution().divide(-2147483648, -1) # -2147483648
2**31 # 2147483648
- 2**31 // -1 # 2147483648
Solution().divide(2147483647, 1)

Extra¶

Unbounded version of the algorithm¶

How would you rewrite the algorithm for unbounded integers?

Right now we're iterating with this for shift in range(31, -1, -1):.

Use the highest useful shift derived from the operands instead of hardcoding 31.

The key observation is:

if b << shift <= a
then the largest possible shift is about $$ \lfloor \log_2(a) \rfloor - \lfloor \log_2(b) \rfloor $$
in Python, that is exactly what bit_length() gives you.

A clean unbounded-integer version is:

class Solution:
    def divide(self, dividend: int, divisor: int) -> int:
        if divisor == 0:
            raise ZeroDivisionError("division by zero")

        if dividend == 0:
            return 0

        negative = (dividend < 0) != (divisor < 0)
        a = abs(dividend)
        b = abs(divisor)

        quotient = 0

        # Largest shift such that b << shift might still fit into a.
        shift = a.bit_length() - b.bit_length()

        for k in range(shift, -1, -1):
            if (b << k) <= a:
                a -= b << k
                quotient |= 1 << k

        return -quotient if negative else quotient

Why this works:

a.bit_length() is the number of bits needed to represent a
so the difference in bit lengths tells you the top candidate shift
then you scan downward once, exactly like binary long division

Complexity in the unbounded model:

the loop runs shift + 1 times
that is $O(\log a - \log b + 1)$
so usually stated as: $$ O(\log |dividend|) $$

One subtle point:

in theoretical big-integer cost models, even <<, <=, and - are not truly $O(1)$ because big integers have many machine words
but in interview-style analysis, we usually count those as constant-time primitive integer ops

If you want the same idea written as a while loop instead of a for loop:

class Solution:
    def divide(self, dividend: int, divisor: int) -> int:
        if divisor == 0:
            raise ZeroDivisionError("division by zero")

        if dividend == 0:
            return 0

        negative = (dividend < 0) != (divisor < 0)
        a = abs(dividend)
        b = abs(divisor)

        quotient = 0
        k = a.bit_length() - b.bit_length()

        while k >= 0:
            shifted = b << k
            if shifted <= a:
                a -= shifted
                quotient |= 1 << k
            k -= 1

        return -quotient if negative else quotient

This is the same algorithm, just expressed more directly.