Leetcode–Divide Two Integers

The Problem:

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

Notes:

  1. This is a tricky problem. Note that Integer range is MAX = 2147 483 647, MIN =- 2147 483 648, so the min number can not be processed by 0-x as common negative number, it will exceed the integer range. MIN value should be taken care of separately. Especially if the dividend is MIN, then to avoid exceeding the range, should add divisor to the dividend first and record 1 in result, then process as normal negative number.
  2. Directly use dividend-divisor will cost too much time when dividend is much larger than divisor. Since we can’t use multiplication, bit manipulation is a good alternative. Note that a<<1 is not a statement, should use a=a<<1

Java Solution

public class Solution {
    public int divide(int dividend, int divisor) {
        boolean neg = false;
        int res = 0;
        // take care of MIN
        if(divisor==Integer.MIN_VALUE && dividend==Integer.MIN_VALUE) return 1;
        if(divisor==Integer.MIN_VALUE) return 0;
        if(dividend ==Integer.MIN_VALUE){
            //---!!!---will exceed range, decrease by divisor and record 1 in result
            res++;
            dividend += Math.abs(divisor);
        }
        
        if(dividend < 0){
            dividend = 0-dividend;
            neg = !neg;
        }
        if(divisor <0){
            divisor = 0-divisor;
            neg = !neg;
        }
        
        int k = 0;
        while(dividend-divisor > divisor){ 
            // don't use dividend> divisor, that results in one unnecessary iteration
            divisor= divisor<<1;
            k++;
        }
        while(k>=0){
            while(dividend >= divisor){
                dividend-=divisor;
                res += 1<<k;
            }
            k--;
            divisor = divisor>>1;
        }
        if(neg)
            return 0-res;
        return res;
    }
}
Advertisements