Divide Two Integers - Leetcode Solution

Problem statement:

Given two integers dividend and divisor, divide the dividend by the divisor and return the quotient.

Assume that the dividend is bound to be a 32-bit signed integer (-231 <= dividend <= 231 - 1), and the divisor is a positive integer.

Return the floor of the integer division. That is, truncating the remainder. For example, 7/3 = 2 and 10/2 = 5.

Example 1:

Input: dividend = 10, divisor = 3

Output: 3

Explanation: 10/3 = truncate(3.33) = 3.

Example 2:

Input: dividend = 7, divisor = -3

Output: -2

Explanation: 7/-3 = truncate(-2.33) = -2.

Solution:

We can solve this problem using binary search. Let's consider an example, dividend = 15 and divisor = 3. The quotient should be 5 i.e. 15/3 = 5. We can find the answer by continuously subtracting the divisor from the dividend until the dividend becomes less than the divisor. The number of times the divisor is subtracted gives us the quotient. This approach takes O(dividend) time in the worst case.

An optimized approach is to use binary search where we repeatedly divide the dividend by the divisor until either dividend becomes less than the divisor or equal to zero. The number of times divisor is divided gives us the quotient. The time complexity of the binary search approach is O(log(dividend)).

Algorithm:

1. We declare variables for the dividend and divisor.

2. We find the signs of the dividend and divisor. i.e. is the quotient going to be positive or negative.

3. We take the absolute values of the dividend and divisor.

4. We declare 3 variables for the quotient, left, and right.

5. We run a while loop until the dividend is greater than or equal to the divisor.

6. We check if divisor is greater than dividend/2. If it is, then we cannot subtract it anymore, so we break the loop.

7. We set left to 1 and right to dividend.

8. We run a binary search while left is less than or equal to right.

   • We find the mid-point of left and right.

   • We check if mid*divisor is greater than the dividend. If it is, we update right to mid - 1.

   • Else, we update left to mid + 1 and quotient to mid.

9. We return the quotient with the sign.

Code:

class Solution:
    def divide(self, dividend: int, divisor: int) -> int:
        if dividend == 0:
            return 0

        sign = (dividend < 0) == (divisor < 0)
        dividend, divisor = abs(dividend), abs(divisor)
        
        quotient = 0
        while dividend >= divisor:
            if divisor > dividend/2:
                break
            left, right = 1, dividend
            while left <= right:
                mid = (left + right) // 2
                if mid * divisor > dividend:
                    right = mid - 1
                else:
                    quotient = mid
                    left = mid + 1
        
            dividend -= quotient * divisor
        
        if sign:
            return min(quotient, 2**31-1)
        else:
            return max(-quotient, -2**31)

1