Divide Two Integers

Question

Divide two integers without using multiplication, division and mod operator.

If it is overflow, return MAX_INT.

Tags

• Maths

Thought

The most simplest idea is to remove the divisor in the while loop until the dividend is smaller than the divisor. However, the time complexity is O(dividend/divisor) and when divisor is too small, the time complexity would be large. For example, when dividend is close to max integer and the divisor is 1, it might cause the time limit exceed. Thus, we need to find another solution.

In the solution provided below, the time complexity is O(log(dividend/divisor)), which is much smaller than the linear time complexity.

Code

class Solution(object):
    def divide(self, dividend, divisor):
        """
        :type dividend: int
        :type divisor: int
        :rtype: int
        """
        # https://discuss.leetcode.com/topic/8714/clear-python-code
        positive = (dividend < 0) is (divisor < 0)
        dividend, divisor = abs(dividend), abs(divisor)
        res = 0
        while dividend >= divisor:
            temp, i = divisor, 1
            while dividend >= temp:
                dividend -= temp
                res += i
                i <<= 1
                temp <<= 1
        if not positive:
            res = -res
        return min(max(-2147483648, res), 2147483647)