Problem Description

The "Divide Two Integers" problem asks you to divide two integers, dividend and divisor, without using multiplication, division, or modulo operators. The result should be the quotient after dividing dividend by divisor. If the division result overflows (i.e., is outside the range of a 32-bit signed integer), you must return 231 - 1 (which is 2147483647). Both dividend and divisor are 32-bit signed integers. The division should truncate toward zero (i.e., discard the fractional part).

• You cannot use multiplication (*), division (/), or modulo (%) operators.
• Return the quotient after dividing dividend by divisor.
• If the result overflows, return 2147483647.

Thought Process

At first glance, dividing without the division operator seems tricky. The most basic approach is repeated subtraction: subtract the divisor from the dividend until the dividend becomes less than the divisor. Each subtraction counts as one toward the quotient. However, this method is inefficient for large numbers, as it could require billions of iterations.

To optimize, we can use bit manipulation. If we can subtract larger multiples of the divisor at once, we can reduce the number of steps. This is similar to how we do long division by hand, taking away the biggest possible chunk each time. By doubling the divisor (using left shifts), we can quickly find how many times the divisor fits into the remaining dividend and accumulate the answer efficiently.

Solution Approach

Here's how we can efficiently solve the problem step-by-step:

1. Handle Edge Cases:
   • If dividend is INT_MIN and divisor is -1, return INT_MAX to prevent overflow.
   • If divisor is 1 or -1, simply return dividend or -dividend (handling overflow).
2. Work with Positive Numbers:
   • Convert both numbers to negatives (to avoid overflow, since INT_MIN has no positive counterpart).
   • Keep track of whether the result should be positive or negative based on input signs.
3. Bitwise Doubling:
   • For each iteration, double the divisor (using left shift) as much as possible without exceeding the dividend.
   • Subtract the largest found multiple from the dividend and add the multiple to the result.
   • Repeat until the dividend is less than the divisor.
4. Apply Sign:
   • If the original numbers had different signs, negate the result.
5. Clamp Result:
   • Ensure the result is within the 32-bit signed integer range.

This approach is efficient because each time we subtract the largest possible chunk, reducing the number of iterations to O(log N).

Example Walkthrough

Let's use the example: dividend = 43, divisor = 8.

1. Both numbers are positive, so the result will be positive.
2. Initialize quotient = 0.
3. Find the largest double of 8 that is less than or equal to 43:
   • 8 << 0 = 8
   • 8 << 1 = 16
   • 8 << 2 = 32
   • 8 << 3 = 64 (too big)
   So, 32 is the largest. Subtract 32 from 43, leaving 11. Add 4 (2²) to the quotient.
4. Repeat with 11:
   • 8 << 0 = 8
   • 8 << 1 = 16 (too big)
   So, 8 is the largest. Subtract 8 from 11 (leaving 3), add 1 to the quotient.
5. Now, 3 is less than 8, so we're done.
6. The quotient is 4 + 1 = 5.

The process quickly reduces the dividend by subtracting large chunks, making it much faster than repeated subtraction.

Time and Space Complexity

• Brute-force Approach: O(N), where N is the absolute value of the quotient. For large numbers, this is extremely slow.
• Optimized Approach (Bit Manipulation): O(log N), where N is the absolute value of the dividend. Each loop iteration reduces the problem size by a factor of two.
• Space Complexity: O(1), as we use only a constant amount of extra space.

Summary

The "Divide Two Integers" problem demonstrates how to implement division without using the division operator, by leveraging bit manipulation and subtraction. The key insight is to subtract the largest possible multiples of the divisor using left shifts, mimicking the process of long division for efficiency. This reduces the number of steps from linear to logarithmic, making the solution both elegant and practical.

Code Implementation

class Solution:
    def divide(self, dividend: int, divisor: int) -> int:
        INT_MAX = 2 ** 31 - 1
        INT_MIN = -2 ** 31

        # Handle overflow
        if dividend == INT_MIN and divisor == -1:
            return INT_MAX

        # Determine sign
        negative = (dividend < 0) != (divisor < 0)

        dividend, divisor = abs(dividend), abs(divisor)
        quotient = 0

        for i in range(31, -1, -1):
            if (dividend >> i) >= divisor:
                quotient += 1 << i
                dividend -= divisor << i

        return -quotient if negative else quotient
      

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

        bool negative = (dividend < 0) != (divisor < 0);
        long long dvd = abs((long long)dividend);
        long long dvs = abs((long long)divisor);
        int quotient = 0;

        for (int i = 31; i >= 0; i--) {
            if ((dvd >> i) >= dvs) {
                quotient += 1 << i;
                dvd -= dvs << i;
            }
        }
        return negative ? -quotient : quotient;
    }
};
      

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

        boolean negative = (dividend < 0) != (divisor < 0);
        long dvd = Math.abs((long)dividend);
        long dvs = Math.abs((long)divisor);
        int quotient = 0;

        for (int i = 31; i >= 0; i--) {
            if ((dvd >> i) >= dvs) {
                quotient += 1 << i;
                dvd -= dvs << i;
            }
        }
        return negative ? -quotient : quotient;
    }
}
      

var divide = function(dividend, divisor) {
    const INT_MAX = 2147483647;
    const INT_MIN = -2147483648;
    if (dividend === INT_MIN && divisor === -1) return INT_MAX;

    let negative = (dividend < 0) !== (divisor < 0);
    let dvd = Math.abs(dividend);
    let dvs = Math.abs(divisor);
    let quotient = 0;

    for (let i = 31; i >= 0; i--) {
        if ((dvd >> i) >= dvs) {
            quotient += 1 << i;
            dvd -= dvs << i;
        }
    }
    return negative ? -quotient : quotient;
};