Divide Two Integers

Problem Id: 29 Difficulty: Medium Tag: Math Tag: Binary Search


Intuition

The basic idea of this solution is to use substraction to solve it.

res = 0
while dividend > 0:
    dividend -= divisor
    res += 1

However, the worst case of this solution would be O(n). If dividend is 2**32 - 1 and divisor is 1, n would be 2**31 - 1 which is too slow.

Instead of substract divisor directly, we can construct divisor ** (2 * k) by using divisor<<k operactor. And each time we find the biggest k where (divisor << k) < dividend.

Solution


class Solution:
    def divide(self, dividend: int, divisor: int) -> int:
        res = 0
        if dividend == 0:
            return 0
        neg = (dividend < 0 and divisor > 0) or (dividend > 0 and divisor < 0)
        dividend, divisor = abs(dividend), abs(divisor)

        while dividend >= divisor:
            k = 1
            superDivisor = divisor
            while (superDivisor << 1) < dividend:
                k = k << 1
                superDivisor = superDivisor << 1
            dividend -= superDivisor
            res += k

        if neg:
            res = - res
        if - 2 ** 31 <= res < 2 ** 31:
            return res
        return 2 ** 31 - 1