29_Divide Two Integers

[Medium] [Math, Binary Search]

Given two integers dividendand divisor, divide two integers without using multiplication, division and mod operator. Return the quotient after dividing dividendby divisor. The integer division should truncate toward zero.

Example 1:

Input: dividend = 10, divisor = 3
Output: 3

Example 2:

Input: dividend = 7, divisor = -3
Output: -2

Solution 1: Linear Search

Idea:

• Deduct divisor from dividend many times. Record how many times it takes until dividend is less than divisor.

Time Complexity: $O(n)$, where n is the output (quotient).

Space Complexity: $O(1)$

def divide(dividend, divisor):
    """
    :type dividend: int
    :type divisor: int
    :rtype: int
    """
    positive = (dividend < 0) == (divisor < 0)             
    dividend, divisor = abs(dividend), abs(divisor)

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

    if not positive:
        return max(-output, -2147483648)
    else:
        return min(output, 2147483647)

Solution 2: Binary Search ??

整数近似除法：32/3 = 10

显然求近似除法可以用乘法来二分查找：32 ~ 3*10 = 3*[1*(2^3) + 0*(2^2) + 1*(2^1) + 0*(2^0)]

res = 0

1. 先找到a使x*2^a <= y < x*2^(a+1)，res += 2^a，y = y - x*2^a

2. if(y >= x*2^(a-1) {res+=2^(a-1); y = y - x*2^(a-1);}

3. if(y >= x*2^(a-2) {res+=2^(a-2); y = y - x*2^(a-2);}

...

但题目不允许用乘法，可以用移位代替：x*2^i = x<<i：

Time Complexity: $O(\log{n})$, where n is the output (quotient).

Space Complexity: $O(1)$

def divide(dividend, divisor):
    """
    :type dividend: int
    :type divisor: int
    :rtype: int
    """
    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)