Divide two integers without using multiplication, division and mod operator.
Solution O(log n)
public class Solution {
public int divide(int dividend, int divisor) {
int sign = 1;
if(dividend < 0){
sign *= -1;
}
if(divisor < 0){
sign *= -1;
}
long a = Math.abs((long)dividend);
long b = Math.abs((long)divisor);
int count = 0;
while(a >= b){
long temp = b;
int mul = 1;
while(a >= temp){
count += mul;
a -= temp;
temp += temp;
mul += mul;
}
}
return count * sign;
}
}
Key concept: Use long to avoid Integer overflow and use binary decode to get the answer
沒有留言:
張貼留言