22ms c++ code use binarysearch and quickmultiply


  • 0
    A

    1.except the sign of dividend and divisor
    let a = dividend and b = divisor
    we want to know the ans = a/b
    and except the overflow
    the range of ans must be 0 ~ INT_MAX
    so we can find ans in range 0~INT_MAX use binarysearch
    if ans is out of the range,so we return INT_MAX
    2.use add operation to instead of multiply operation
    suppose b equal 11 = 1011B a equal 3
    b = 11a + 12a + 04a + 18a

    class Solution {
    public:
    	long long qmul(long long  a,long long  b){ //a*b
    		long long ans = 0;
    		for(;b>0;b>>=1,a+=a) if(b&1) ans+=a;
    		return ans; 
    	}
    	int divide(int dividend, int divisor) {
    		long long ans;
    		long long left = 0;
    		long long right = (long long)INT_MAX+10;
    		long long mid = 0;
    		if(divisor == 0) return INT_MAX;
    		if(dividend == 0) return 0;
    		long long divisor_tmp = divisor;
    		long long dividend_tmp = dividend;
    		bool flag = ((long long)divisor*dividend < 0);
    		divisor_tmp = divisor_tmp < 0 ? -divisor_tmp : divisor_tmp;
    		dividend_tmp = dividend_tmp < 0 ? - dividend_tmp: dividend_tmp;
    		while(right - left > (long long)1 ){
    		//printf("%lld %lld\n",left,right);
    			mid = ( left + right ) >> 1;
    			if( qmul(mid,divisor_tmp) <= dividend_tmp)
    				left = mid;
    			else 
    				right = mid;
    		}
    		ans = left;
    		if(flag) ans = -ans;
    		if(ans < INT_MIN || ans > INT_MAX)
    			ans = INT_MAX;
    		return (int)ans;  
    	};
    };
    

Log in to reply
 

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