Problem Statement in English

You’re given two integers, dividend and divisor. Divide the dividend by the divisor without using multiplication, division, and mod operator.

Approach

Doing repeated subtraction is a brute force approach, but it will be too slow for large numbers. Instead, we can use bit manipulation to speed up the process.

The idea is to double the divisor (using left shift) until it exceeds the dividend, and then subtract it from the dividend. We keep track of how many times we can subtract the doubled divisor from the dividend, which gives us the quotient.

We take the remainder and repeat the process until the dividend is less than the divisor.

The previous quotient is added to the current quotient, and we continue until the dividend is less than the divisor.

When it’s finally done, we return the quotient with the appropriate sign.

The sign is the XOR of the signs of the dividend and divisor. If they have different signs, the result is negative; otherwise, it’s positive.

The one edge case we need to handle is when the dividend is -2^31 and the divisor is -1, which would cause an overflow. In this case, we return 2^31 - 1.

And we’re done!

Solution in Python


class Solution:
    def divide(self, dividend: int, divisor: int) -> int:
    # Handle 32-bit signed integer overflow edge case
        INT_MAX = 2**31 - 1
        INT_MIN = -2**31

        if dividend == INT_MIN and divisor == -1:
            return INT_MAX

        # Determine sign of the result
        negative = (dividend < 0) ^ (divisor < 0)

        # Convert to positive values using abs()
        dvd = abs(dividend)
        dvs = abs(divisor)
        quotient = 0

        # Exponential subtraction using bit shifts
        while dvd >= dvs:
            temp_dvs = dvs
            multiple = 1

            # Double the divisor until it exceeds the remaining dividend
            while dvd >= (temp_dvs << 1):
                temp_dvs <<= 1
                multiple <<= 1

            dvd -= temp_dvs
            quotient += multiple

        return -quotient if negative else quotient

Complexity

  • Time: $O(\log n)$
    Since at every step we are doubling the divisor, the number of iterations is logarithmic with respect to the dividend.

  • Space: $O(1)$
    Since we are using a constant amount of space for variables, the space complexity is constant.

And we are done.