29. Divide Two Integers

/**

 * 29. Divide Two Integers

 * Given two integers dividend and divisor, divide two integers without using multiplication, division, and mod

 * operator.

 * Return the quotient after dividing dividend by divisor.

 * The integer division should truncate toward zero, which means losing its fractional part. For example,

 * truncate(8.345) = 8 and truncate(-2.7335) = -2.

  */

See the solution to the problem on github here:

https://github.com/zcoderz/leetcode/blob/main/src/main/java/bitwise/Divide.java

This is a tricky problem. I will explain below ways to simplify the approach to the problem.

Observations:

  • In the approach below, I am handling edge cases around negative numbers. In an interview the approach could be to simply solve the problem for positive numbers and time permitting handle for negative numbers and boundary cases.
  • Negative values add some more edge cases that I have described in the inline comments in code below.
    •  -2^31 / -1 = 2^31 but the max integer value is 2^31 -1 , so handle as special case.
    • In order to handle the case where the dividend is -2^31 (minimum integer value), work with both dividend and divisor as negative numbers and adjust the sign of quotient once calculated appropriately.

Algorithm:

  1. The approach at a high level is rather simple. You converge towards a solution via using powers of 2.
  2. You find the largest power of two which when multiplied by the divisor is still less than then the dividend
  3. You keep subtracting the value calculated in 2 from the dividend while reducing it per iteration by a factor of 2 while dividend is greater than the divisor
    1. You also track the quotient in the loop
      1. quotient += highestPowerOfTwo;
      1. dividend -= highestDouble;
      1. highestPowerOfTwo >>= 1;
      1. highestDouble >>= 1;
  4. You adjust the sign of the quotient based on whether one of divisor and dividend was negative

Here is the code:

/**
 * you could simplify your life by writing this code assuming only positive numbers and then as a second step handle
 * overflow and negative number conditions. for me thinking on the number line rightwards (positive) is mentally
 * much simpler when justifying the conditions....
 *
 */
public int divide(int dividend, int divisor) {
    //Special case: overflow. (-2^31 / -1) = 2^31 which is outside the bounds of int as max int is 2^31-1
    //treat this as a special case
    if (dividend == Integer.MIN_VALUE >&& divisor == -1) {
        return Integer.MAX_VALUE;
    }

    //use neg as a multiplier to adjust sign of final quotient.
    //if both dividend and divisors are negative than quotient is positive , else if one is negative its neg
    //if both are positive, its positive.
    int neg = (divisor < 0) ? -1 : 1;
    neg = (dividend < 0) ? -neg : neg;

    //change dividend and divisor to negative numbers
    //this is so you could handle the case of division of Integer.MIN_VALUE.
    //Integer.MIN_VALUE has no equivalent in positive space as -ive values have an extra value in integers.
    //specifically it is the -2147483648
    dividend = (dividend < 0) ? dividend : -dividend;
    divisor = (divisor < 0) ? divisor : -divisor;

    //trying to fix the highest power of two and the highest divisor multiple (highest double) that can be used
    //>= HALF_INT_MIN is to avoid overflow (we are working in negatives so need to check only the negative side)
    int highestDouble = divisor;
    int highestPowerOfTwo = -1;
    while (highestDouble >= HALF_INT_MIN && dividend <= highestDouble + highestDouble) {
        highestPowerOfTwo += highestPowerOfTwo;
        highestDouble += highestDouble;
    }

    //keep subtracting highest double from dividend until dividend is less than the divisor
    int quotient = 0;
    while (dividend <= divisor) {
        if (dividend <= highestDouble) {
            quotient += highestPowerOfTwo;
            dividend -= highestDouble;
        }
        /* We know that these are always even, so no need to worry about the
         * annoying "bit-shift-odd-negative-number" case. */
        highestPowerOfTwo >>= 1;
        highestDouble >>= 1;
    }

    //adjust to return the quotient based on neg sign
    if (neg != 1) {
        return -quotient;
    }
    return quotient;
}