LeetCode Divide Two Integers: Binary Search and Tricky Overflow Issues

Overview

LeetCode Divide Two Integers:  Simulate the divide by subtraction and bit operation in binary search manner, those tricky overflow issues are addressed too.

LeetCode Divide Two Integers

Divide two integers without using multiplication, division and mod operator.

If it is overflow, return MAX_INT.

Solution and Precautions: Binary Search and Tricky Overflow Issues

Even though we are not allowed to use *, / and %, but we can use minus and bit operator. My solution is based on such a fact that any number could be represented as a polynomial form, for example, 5 = 2^2 + 2^0, 78 = 2^5 + 2^3 + 2^2 + 2^1 and so on, any number could be represented as in this form. Now let’s consider the result quotient represented in this form, the good thing for thinking in this way is that, we now can make use of bit operator, a » 1 = a / 2  a«1 = a * 2. We keep multiply the divisor by 2 (divisor «= 1) until it reaches or larger than half the dividend (because if we multiply it by 2 again, it will be larger than the dividend), we then subtract this value from the dividend, and here, suppose this value is divisor * 2^k, then 2^k needs to be added into the final quotient result (remember we represent the quotient in a polynomial form), we keep doing this until the dividend becomes zero. Another good point of this method is that we could find the quotient in log time since we always multiply the divisor by 2 by2, in the log time the divisor will reaches the dividend. The following Java code is accepted by LeetCode OJ to pass this Divide Two Integers problem:

public class Solution {
    private int absolute(int a) {
        if (Integer.MIN_VALUE == a)
            return Integer.MAX_VALUE;

        return a > 0 ? a : -a;
    }

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

        if (0 == divisor)
            return Integer.MAX_VALUE;

        boolean sign = (dividend > 0 && divisor > 0) || (dividend < 0 && divisor < 0); 
        
        if (dividend == divisor)
            return 1;

        if (Math.abs(divisor) == 1)
            return divisor == 1 ? dividend : -dividend;

        if (Math.abs(divisor) == 2)
            return divisor == 2 ? dividend >> 1 : -(dividend >> 1);

        if (0 == dividend)
            return 0;

        if (Integer.MIN_VALUE == divisor)
            return 0;


        dividend = absolute(dividend);  
        divisor  = absolute(divisor); 

        int q = 0;
        int substract = 0;
        int bitToSet = 0;
        int endValue = 0;
        while (dividend >= divisor) {
             
            substract = divisor;
            bitToSet = 1;
            endValue = (dividend >> 1);  

            while (endValue >= substract) {
                substract <<= 1;
                bitToSet  <<= 1;
            }

            q |= bitToSet;
            dividend -= substract;
        }
        return sign ? q : -q;
    }
}

As you can see from the above code, special cases need to be carefully addressed, another alternative could be using long long in C++ or long type in Java.

Several other issues worth noting

(1) sign, always check the different signs of the dividend and the divisor and the above approach only applies when both of them are positive, it is ok here since we can always convert negative into positive and keeping record of the final sign

(2) the overflow issue is very annoying in the problem, be careful about things like INT_MAX, INT_MIN

(3) Again! Be very careful on the overflow issues here. The following are some test cases which you might be concerned about (I was incorrectly addressed):

// Input:   -2147483648, -1
// Output:  -2147483648
// Expected: 2147483647
//
// Input:   -2147483648, -1
// Output:  -2147483648
// Expected: 2147483647
//
//
// Input:   2147483647, -2147483648
// Output:  -1
// Expected: 0
//
// Input:   -2147483648, -2147483648
// Output:   0
// Expected: 1

Summary

LeetCode Divide Two Integers:  Simulate the divide by subtraction and bit operation in binary search manner, those tricky overflow issues are addressed too.

Written on May 6, 2013