LeetCode 29 - Divide Two Integers

Question:

Given two integers dividend and divisor, divide two integers without using multiplication, division, and mod operator.

The integer division should truncate toward zero, which means losing its fractional part. For example, 8.345 would be truncated to 8, and -2.7335 would be truncated to -2.

Return the quotient after dividing dividend by divisor.

Note: Assume we are dealing with an environment that could only store integers within the 32-bit signed integer range: [−231, 231 − 1]. For this problem, if the quotient is strictly greater than 231 - 1, then return 231 - 1, and if the quotient is strictly less than -231, then return -231.

Example 1:

Input: dividend = 10, divisor = 3

Output: 3

Explanation: 10/3 = 3.33333.. which is truncated to 3.

Example 2:

Input: dividend = 7, divisor = -3

Output: -2

Explanation: 7/-3 = -2.33333.. which is truncated to -2.

Answer:

If we read the description of the problem, it looks like that this is a simple division problem. However, if we read further, we find a constraint that we cannot use multiplication (x), division (/) and modulo (%) operations. This makes this problem a little tricky.

Also, one more constraint is that the result cannot be greater than 32-bit signed integer (from -231 to 231 - 1). If the result is outside this range, then we will return the minimum or maximum value of this range.

Approach:

The first idea is to start with a quotient of 0 and keep subtracting the divisor from the dividend until the dividend is smaller than the divisor. While this approach works, it's slow for large numbers because it can take many iterations.

To speed things up, we can try a different method. Instead of subtracting the divisor linearly, we'll subtract it exponentially. Here's how:

We'll start with a quotient variable to keep track of the answer.
We'll use a while loop to check if the dividend is greater than or equal to the divisor.
Inside the loop, we'll use another variable called "shift" to left shift the divisor by one bit and check if the result is less than the dividend. We'll repeat this until the condition is false.
Once we're out of the inner loop, we'll add the number of times we shifted to the quotient.
We'll subtract the result of shifting from the dividend for the next iteration. Since the shifting may have gone beyond the dividend in the loop, we subtract one less bit.
We'll keep repeating this process until the divisor is greater than the dividend.

Why do we shift the bits? Shifting a number to the left by one bit doubles its value. Since we can't use multiplication, we're using left shifting as an alternative.

Time Complexity:

O(log n)

Space Complexity:

O(1)

Code:

class DivideTwoIntegers:
    def divide(dividend: int, divisor: int) -> int:
        # MAX and MIN values for integer
        MAX = 2147483647
        MIN = -2147483648
        # Check for overflow
        if divisor == 0 or (dividend == MIN and divisor == -1):
            return MAX
        # Sign of result`
        sign = -1 if (dividend > 0 and divisor < 0) or (dividend < 0 and divisor > 0) else 1
        # Quotient
        quotient = 0
        # Take the absolute value
        absoluteDividend = abs(dividend)
        absoluteDivisor = abs(divisor)
        # Loop until the  dividend is greater than divisor
        while absoluteDividend >= absoluteDivisor:
            # This represents the number of bits shifted or
            # how many times we can double the number
            shift = 0
            while absoluteDividend >= (absoluteDivisor << shift):
                shift += 1
            # Add the number of times we shifted to the quotient
            quotient += (1 << (shift - 1))
            # Update the dividend for the next iteration
            absoluteDividend -= absoluteDivisor << (shift - 1)
        return -quotient if sign == -1 else quotient