29. Divide Two Integers

Description

The problem is to implement a function that performs division of two integers without using multiplication, division, and mod operators. The result should be an integer. If the result overflows, it should return the maximum integer value possible.

Intuition

The problem can be approached by simulating the division process using subtraction. The key observation is that repeated subtraction can be optimized by doubling the divisor repeatedly, similar to how binary long division works. This allows us to subtract large chunks at a time, which speeds up the process.

Approach

1. Handle the edge case where dividing -2147483648 by -1 would result in an overflow. Return 2147483647 in this case.
2. Check if either the dividend or divisor is negative to determine the sign of the result.
3. Convert both the dividend and divisor to their absolute values.
4. Use a loop to repeatedly subtract the divisor from the dividend while shifting the divisor left (multiplying by 2) each time to efficiently find the quotient.
5. Adjust the quotient according to the sign determined earlier.
6. Return the final quotient.

Complexity

Time Complexity:

O(log n), where n is the absolute value of the dividend. The divisor is doubled in each iteration, which makes the operation logarithmic.

Space Complexity:

O(1), as only a few extra variables are used.

Code

C++

class Solution {
public:
    int divide(int dividend, int divisor) {
        if (dividend == INT_MIN && divisor == -1) return INT_MAX;
        if (abs(divisor) == 1) return dividend * divisor;

        bool isNegative = (dividend < 0) ^ (divisor < 0);
        int count = 0;

        long long absDividend = abs((long long)dividend);
        long long absDivisor = abs((long long)divisor);

        while (absDividend >= absDivisor) {
            long long base = absDivisor;
            int x = 1;
            while (base <= (absDividend >> 1)) {
                base <<= 1;
                x <<= 1;
            }
            count += x;
            absDividend -= base;
        }

        return isNegative ? -count : count;
    }
};

Python

class Solution:
    def divide(self, dividend: int, divisor: int) -> int:
        if dividend == -2147483648 and divisor == -1:
            return 2147483647
        if abs(divisor) == 1:
            return dividend * divisor

        is_negative = (dividend < 0) ^ (divisor < 0)
        count = 0

        dividend, divisor = abs(dividend), abs(divisor)

        while dividend >= divisor:
            x = 1
            base = divisor
            while base <= (dividend >> 1):
                base <<= 1
                x <<= 1
            count += x
            dividend -= base

        return -count if is_negative else count

Java

class Solution {
    public int divide(int dividend, int divisor) {
        if (dividend == Integer.MIN_VALUE && divisor == -1) return Integer.MAX_VALUE;
        if (Math.abs(divisor) == 1) return dividend * divisor;

        boolean isNegative = (dividend < 0) ^ (divisor < 0);
        int count = 0;

        long absDividend = Math.abs((long)dividend);
        long absDivisor = Math.abs((long)divisor);

        while (absDividend >= absDivisor) {
            long base = absDivisor;
            int x = 1;
            while (base <= (absDividend >> 1)) {
                base <<= 1;
                x <<= 1;
            }
            count += x;
            absDividend -= base;
        }

        return isNegative ? -count : count;
    }
}

JavaScript

var divide = function (dividend, divisor) {
    if (dividend === -2147483648 && divisor === -1) return 2147483647
    if (Math.abs(divisor) === 1) return dividend * divisor;

    let isNegative = false;
    let count = 0;

    if ((dividend < 0 || divisor < 0) && !(dividend < 0 && divisor < 0))
        isNegative = true;

    dividend = Math.abs(dividend);
    divisor = Math.abs(divisor);

    while (dividend >= divisor) {
        let x = 1;
        base = divisor;
        while (base <= (dividend >> 1)) {
            base = base << 1;
            x = x << 1;
        }
        count += x;
        dividend -= base;
    }

    if (isNegative) return -count;
    return count;
};