Description
Divide two integers without using multiplication, division and mod operator.
If it is overflow, return MAX_INT.
Solution
Binary search, time O(logn), space O(1)
比较蛋疼的题...起初想用减法做，但O(n)的时间会TLE，改成用加法做，利用类似二分的方式加速。
class Solution {
public int divide(int dividend, int divisor) {
if (divisor == 0) {
return Integer.MAX_VALUE;
}
long x = dividend;
long y = divisor;
int sign = (x < 0 && y > 0) || (x > 0 && y < 0) ? -1 : 1;
x = Math.abs(x);
y = Math.abs(y);
long z = divide(x, y);
if (sign > 0 && z > Integer.MAX_VALUE) { // overflow
return Integer.MAX_VALUE;
}
return (int) (sign * z);
}
public long divide(long x, long y) {
if (x < y) {
return 0;
}
long sum = y;
long multiple = 1;
// Find the largest multiple so that (divisor * multiple <= dividend),
// moving with stride 1, 2, 4, 8, 16...2^n for performance reason
while ((sum << 1) <= x) {
sum <<= 1;
multiple <<= 1;
}
return multiple + divide(x - sum, y);
}
}
