Divide Two Integers

Problem: Divide Two Integers

The general idea of solving this problem is use double to quickly approach the target. For example, if we want to calculate 10/2, we can make 2 double as 4 and 8, and get 2 times 4 equals 8 (1+1=2, 2+2=4). 10 mod 8 equals 2, and we calculate how much times 2 equals 2.

Code in Python:

class Solution(object):
    def divide(self, dividend, divisor):
        """
        :type dividend: int
        :type divisor: int
        :rtype: int
        """
        MAX_INT=2147483647
        if divisor == 0:
            return MAX_INT
        if abs(dividend) < abs(divisor) or dividend == 0:
            return 0
        if (dividend > 0 and divisor < 0) or (dividend < 0 and divisor > 0):
            pos = -1
        else:
            pos = 1
        dividend, divisor = abs(dividend), abs(divisor)

        times, prod = 1, divisor
        while prod + prod < dividend:
            times += times
            prod += prod
        times += self.divide(dividend - prod, divisor)

        return min(pos*times, MAX_INT)

Details:

• Use a positive flag to deal with positive and negative.
• Mind the overflow

We can also use bit operation to accelerate our program.

Code in Java:

public class Solution {
    public int divide(int dividend, int divisor) {
        //try to know if the result is positive or negative
        Boolean positive=true;
        if(dividend>=0&&divisor>0||dividend<=0&&divisor<0){
            positive=true;
        }else if(dividend<=0&&divisor>0||dividend>=0&&divisor<0){
            positive=false;
        }else{
            return Integer.MAX_VALUE;
        }

        //First turn it to long to make the operations easier
        long ldividend=Math.abs((long)dividend);
        long ldivisor=Math.abs((long)divisor);
        long result=0;
        while(ldividend>=ldivisor){
            long tmpDivisor=ldivisor;
            long tmpResult=1;
            //use bit manipulation to get the biggest result once a time
            while((tmpDivisor<<1)<ldividend){tmpDivisor<<=1;tmpResult<<=1;}
            ldividend-=tmpDivisor;
            result+=tmpResult;
        }
        //what should do when result is larger than the MAX
        if(result>Integer.MAX_VALUE&&positive)
            return Integer.MAX_VALUE;
        if(result>Integer.MAX_VALUE&&!positive)
            return Integer.MIN_VALUE;
        if(positive){
            return (int)result;
        }else{
            return -1*(int)result;
        }
    }
}