Problem Statement

Write a function that calculates the quotient of two integers dividend and divisor without using the multiplication (*), division (/), or modulo (%) operators.

The result should be truncated toward zero (e.g., truncate(8.345) = 8, truncate(-2.7335) = -2).

Assume the environment only supports 32-bit signed inteegers, ranging from -2^31 to 2^31 - 1. If the division result overflows, return 2^31 - 1.

JavaScript Number Representation

JavaScript uses a single Number type based on the IEEE 754 double-precision 64-bit format. This means there is no distinct integer type; numbers are stored as floating-point values.

The maximum safe integer value is Number.MAX_SAFE_INTEGER (2^53 - 1), and the minimum is Number.MIN_SAFE_INTEGER (-2^53 + 1). Operations outside this "safe" range may suffer from rounding errors.

let maxSafe = Number.MAX_SAFE_INTEGER;
console.log(maxSafe + 1 === maxSafe + 2); // true (due to precision loss)

let minSafe = Number.MIN_SAFE_INTEGER;
console.log(minSafe - 1 === minSafe - 2); // true

You can verify if a number is safe using Number.isSafeInteger.

Basic Subtraction Approach

Since we cannot use division, the most straightforward method is to repeatedly subtract the divisor from the dividend until the remainder is smaller than the divisor. The count of subtractions is the quotient.

Example: Calculating 9 / 2:

1. 9 - 2 = 7 (Count: 1)
2. 7 - 2 = 5 (Count: 2)
3. 5 - 2 = 3 (Count: 3)
4. 3 - 2 = 1 (Count: 4)

Since 1 < 2, the loop stops. The result is 4.

function calculateQuotient(dividend, divisor) {
    let count = 0;
    while (dividend >= divisor) {
        dividend -= divisor;
        count++;
    }
    return count;
}

Handling Negative Numbers

To handle negative values, we first determine the sign of the result. If the signs of the dividend and divisor differ, the result is negative. We can use the XOR operator (^) for this logic.

After determining the sign, we convert both numbers to their absolute values to perform the subtraction logic on positive numbers.

function calculateQuotient(dividend, divisor) {
    const isNegative = (dividend > 0) ^ (divisor > 0);
    
    let num = Math.abs(dividend);
    let den = Math.abs(divisor);
    let count = 0;

    while (num >= den) {
        num -= den;
        count++;
    }

    return isNegative ? -count : count;
}

Addressing 32-bit Overflow

The constraint specifies a 32-bit signed integer range. The only case where the result overflows is when dividend is -2^31 and divisor is -1. The mathematical result would be 2^31, which exceeds the maximum positive value of 2^31 - 1.

We must handle this edge case explicit before processing.

function calculateQuotient(dividend, divisor) {
    // Handle overflow edge case
    if (dividend === -(2**31) && divisor === -1) {
        return 2**31 - 1;
    }

    const isNegative = (dividend > 0) ^ (divisor > 0);
    let num = Math.abs(dividend);
    let den = Math.abs(divisor);
    let count = 0;

    while (num >= den) {
        num -= den;
        count++;
    }

    return isNegative ? -count : count;
}

Optimization: Exponential Subtraction

The basic subtraction approach has a time complexity of O(N), which is inefficient for large dividends (e.g., 2^31 / 1). We can optimize this to O(log N) by subtracting larger chunks at a time.

Instead of subtracting den one by one, we check if we can subtract den * 2, den * 4, den * 8, etc. We double the subtracted value in each inner loop iteration.

Example: 15 / 2

1. 15 >= 2. Double 2 to 4, then 8. 15 >= 8. Subtract 8 (add 4 to result). Remainder: 7.
2. 7 >= 2. Double 2 to 4. 7 >= 4. Subtract 4 (add 2 to result). Remainder: 3.
3. 3 >= 2. 3 < 4. Subtract 2 (add 1 to result). Remainder: 1.
4. Stop. Result = 4 + 2 + 1 = 7.

Final Implementation

The following solution implements the optimized logic. Note that we avoid the * operator by using addition (e.g., increment += increment instead of increment * 2).

/**
 * @param {number} dividend
 * @param {number} divisor
 * @return {number}
 */
var divide = function(dividend, divisor) {
    // Edge case for overflow
    if (dividend === -(2**31) && divisor === -1) {
        return 2**31 - 1;
    }

    // Determine sign
    const negativeResult = (dividend > 0) ^ (divisor > 0);
    
    let absDividend = Math.abs(dividend);
    let absDivisor = Math.abs(divisor);
    let quotient = 0;

    while (absDividend >= absDivisor) {
        let currentBase = absDivisor;
        let multiplier = 1;

        // Double the base until it exceeds the dividend or the safe limit for doubling
        while (currentBase >= -(2**30) && absDividend >= currentBase + currentBase) {
            multiplier += multiplier;
            currentBase += currentBase;
        }

        quotient += multiplier;
        absDividend -= currentBase;
    }

    return negativeResult ? -quotient : quotient;
};