Leetcode: Divide Two Integers

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

Understand the problem:
The problem gives a dividend and divisor, of which are integer types. Return the division result with int type as well. Note that the problem does not allow to use multiplication, division and mod operator. 

Several special cases need to think about:
For dividend is 0, return 0.
For divisor equals to 0, we check if the dividend is positive or negative, and return the Integer.MAX_VALUE, and Integer.MIN_VALUE, respectively. 
For negative numbers. If either is negative, the result is negative. If both are negative, result is positive. 

Solution:

public class Solution {
    public int divide(int dividend, int divisor) {
        if (dividend == 0) return 0;
        if (divisor == 0 && dividend > 0) return Integer.MAX_VALUE;
        if (divisor == 0 && dividend < 0) return Integer.MIN_VALUE;
        if (divisor == 1) return dividend;
        if (divisor == -1) return -dividend;
        
        boolean isDividendNeg = false;
        boolean isDivisorNeg = false;
        if (dividend < 0) {
            isDividendNeg = true;
            dividend = -dividend;
        }
        if (divisor < 0) {
            isDivisorNeg = true;
            divisor = -divisor;
        }
        
        int result = 0;
        while (dividend > divisor) {
            dividend = dividend - divisor;
            result++;
        }
        
        if ((isDividendNeg == true && isDivisorNeg == false) || 
            (isDividendNeg == false && isDivisorNeg == true))
            result = -result;
            
        return result;
    }
}

The code above has one bug: It does not handle negative number overflow problem. Consider the input -1010369383, -2147483648. The divisor is Integer.MIN_VALUE. When we flip it, it is overflowed. Consider the integer number ranges from -2^31 to 2^31 - 1. 

It is a very common bug in doing integer math arithmetic. The common approach to handle this is to convert the integer to long first. We actually have seen this situation many times before. So the correct code is:

Code (Java):

public class Solution {
    public int divide(int dividend, int divisor) {
        if (dividend == 0) return 0;
        if (divisor == 0 && dividend > 0) return Integer.MAX_VALUE;
        if (divisor == 0 && dividend < 0) return Integer.MIN_VALUE;
        if (divisor == 1) return dividend;
        if (divisor == -1) return -dividend;
        
        long dividendL = (long) dividend;
        long divisorL = (long) divisor;
        
        boolean isDividendNeg = false;
        boolean isDivisorNeg = false;
        if (dividendL < 0) {
            isDividendNeg = true;
            
            dividendL = -dividendL;
        }
        if (divisor < 0) {
            isDivisorNeg = true;
            divisorL = -divisorL;
        }
        
        int result = 0;
        while (dividendL > divisorL) {
            dividendL = dividendL - divisorL;
            result++;
        }
        
        if ((isDividendNeg == true && isDivisorNeg == false) || 
            (isDividendNeg == false && isDivisorNeg == true))
            result = -result;
            
        return result;
    }
}

Discussion:
The implementation above is very inefficient especially when divisor is relative small compared to the dividend. Note that the solution above we deduct the divisor once a time. If we can deduct the divisor in exponential rate, the algorithm could be much faster.  For example, 16 / 3 = 5. In the naive solution, 
16 - 3 = 13
13 - 3 = 11
11 - 3 = 8
8 - 3 = 5
5 - 3 = 2 

We can increase the rate of divisor in exponential rate. 
16 - 3 * 2^1 = 7
16 - 3 * 2^2 = 4
16 - 3 * 2^3 < 0 
So in this case, we can see that the total number of times to shift is 3. We stop at when b is just greater than a, then go back one step where b is just less than a. Then we can calculate the partial result, in this case is 2^2 = 4. We deduct a from b,  and update a. Then we repeat the process again until a is less than b. 

Code (Java):

public class Solution {
    public int divide(int dividend, int divisor) {
        if (dividend == 0) return 0;
        
        boolean isNeg = false;
        if ((dividend > 0 && divisor < 0) || 
            (dividend < 0 && divisor > 0))
            isNeg = true;
        
        long a = Math.abs((long)dividend);
        long b = Math.abs((long)divisor);
        
        int ans = 0;
        
        while (a >= b) {
            int shift = 0;
            while (a >= (b << shift)) {
                shift++;
            }
            
            ans += (1 << (shift - 1));
            a -= b << (shift - 1);
        }
        
        if (isNeg) ans = -ans;
        return ans;
    }
}

Summary:
This is a very interesting problem, but tricky. Two things you must be careful: Integer overflow, and we usually use a longer data type to avoid that. Secondly, the O(logn) solution is very tricky. Do understand the details.