Java 2ms O(log(n)) solution.


  • 1

    Key points: 1. Use bit shift to do binary search.
    2. Watch the overflow condition. That's why both dividend and divisor need to be used as long for calculation.
    3. Take care of negative numbers. I record the original signs and handle both dividend and divisor as positive during calculation(binary search and counter add).

    public class Solution {
    public int divide(int dividend, int divisor) {
        if(divisor==0){
            return Integer.MAX_VALUE;
        }
        else if(dividend==0){
            return 0;
        }
        int sign1 = 1;
        int sign2 = 1;
        long dividend_long = dividend;
        long divisor_long = divisor;
        if(dividend<0){
            sign1 = -1;
            dividend_long = -dividend_long;
        }
        if(divisor<0){
            sign2 = -1;
            divisor_long = -divisor_long;
        }
        long curr = divisor_long;
        long ccount = 1;
        long res = 0;
        while(dividend_long-curr>=curr){
            curr = curr<<1;
            ccount = ccount<<1;
        }
        while(curr>0&&ccount>0){
            while(dividend_long - curr>=0){
                dividend_long = dividend_long-curr;
                res += ccount;
            }
            curr=curr>>1;
            ccount=ccount>>1;
        }
        if(sign1*sign2*res>Integer.MAX_VALUE){
            return Integer.MAX_VALUE;
        }
        else if(sign1*sign2*res<Integer.MIN_VALUE){
            return Integer.MIN_VALUE;
        }
        else{
            return (int)(sign1*sign2*res);
        }
    }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.