[Leetcode] 29. Divide Two Integers

Table of Contents

Description

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: $[-2^{31}, 2^{31} - 1]$. For this problem, if the quotient is strictly greater than $2^{31} - 1$, return $2^{31} - 1$, and if the quotient is strictly less than $-2^{31}$, return $-2^{31}$.

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.

Constraints:

• $-2^{31} \leq \text{dividend}, \text{divisor} \leq 2^{31} - 1$
• divisor != 0

Approach

This problem is solved efficiently by leveraging bit manipulation and a doubling strategy. Instead of performing repeated subtraction, we use bit shifts to quickly find the largest multiples of the divisor that fit into the dividend, accumulating these to compute the quotient. This reduces the number of operations from linear to logarithmic time. The approach also ensures correct handling of signs and overflow cases.

Solution

/**
 * @param {number} dividend
 * @param {number} divisor
 * @return {number}
 */
var divide = function (dividend, divisor) {
  const MAXIMUM_INT = 2147483647;
  const MINIMUM_INT = -2147483648;

  // Determine the sign of the result by checking if dividend and divisor have the same sign
  const isPositiveQuotient = dividend < 0 === divisor < 0;

  // Use absolute values to simplify the division logic
  let absDividend = Math.abs(dividend);
  const absDivisor = Math.abs(divisor);

  if (absDividend < absDivisor) return 0;

  // Handle the overflow edge case: dividing MIN_INT by -1 exceeds max 32-bit int
  if (dividend === MINIMUM_INT && divisor === -1) {
    return MAXIMUM_INT;
  }

  let absQuotient = 0;
  // Loop until the dividend is smaller than divisor
  while (absDividend >= absDivisor) {
    // Initialize multiplier and tempDivisor for doubling strategy
    let multiplier = 1,
      tempDivisor = absDivisor;

    // Double tempDivisor and multiplier while doubling tempDivisor won't overflow 32-bit integer
    while (
      tempDivisor <= MAXIMUM_INT >>> 1 &&
      absDividend >= tempDivisor << 1
    ) {
      tempDivisor = tempDivisor << 1;
      multiplier = multiplier << 1;
    }

    // Subtract the largest doubled divisor from dividend
    absDividend -= tempDivisor;
    // Add the corresponding multiplier to the quotient
    absQuotient += multiplier;
  }

  // Apply the correct sign to the quotient before returning
  return isPositiveQuotient ? +absQuotient : -absQuotient;
};

Complexity Analysis

Time Complexity

The time complexity is $O(\log n)$, where $n$ is the absolute value of the dividend. The while loop iterates logarithmically due to the doubling strategy, significantly reducing the number of iterations compared to a naive approach.

Space Complexity

The space complexity is $O(1)$, as we are using a constant amount of extra space for variables and do not require any additional data structures that grow with the input size.