8ms solution with binary search


  • -1
    B
    long long multiply(long long a, long long b){
    	long long r;
    	for (r = 0; b; b >>= 1){
    		b & 1 && (r += a);
    		a += a;
    	}
    	return r;
    }
    int divide(int dd, int dr) {
    
    	long long i, a, b, n, f = 1, dividend = dd, divisor = dr,m;
    	int r;
    	if (dividend < 0){
    		dividend = -dividend;
    		f = -f;
    	}
    	if (divisor < 0){
    		divisor = -divisor;
    		f = -f;
    	}
    	a = 0;
    	b = dividend + 1;
    	m = (a + b) >> 1;
    	for (; a < b;){
    		n = multiply(m,divisor);
    		if (n > dividend)
    			b = m - 1;
    		else if (n < dividend)
    			a = m + 1;
    		else
    			break;
    		m = (a + b) >> 1;
    	}
    	if (multiply(m, divisor) > dividend) m--;
    
    	r = m;
    	if (r && f>0 && -r == r) r = ~r;
    	return f>0 ? r : -r;
    }

Log in to reply
 

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