This Question is about how to divide two integers without using multiplication, division and mod operator. If it is overflow, return MAX_INT.
I think the essential of the division is about how many divisor are contained in a dividend. First, we can keep the negative sign “-“, then count how many times we have subtracted the divisor from the dividend, at last, put the negative sign back to the result. The edge cases are critical, I enlarge the int to long in div() and abs() methods to avoid the eventual conversion errors.
My approach is to use recursion to repeat the subtraction and at the same time count the result. I tried to program a tail recursion to optimized the computation. But it seems not working, I will explain it later.
public int divide(int dividend, int divisor) {
int res = Integer.MAX_VALUE;
if (divisor != 0) {
res = (int) div(abs(dividend), abs(divisor), 0);
if (dividend > 0 ^ divisor > 0) {
res = 0 - res;
}
}
return res;
}
private long abs(final long x) {
return x < 0 ? 0 - x : x;
}
private long div(final long x, final long y, final long res) {
return x < y ? res : div(x - y, y, res + 1);
}
This solution passes almost all the unit tests except when dividend is quite big and divisor is very small, for example dividend = 2147483647 (MAX_INT), divisor = 1. In this case we will only get stack overflow exception, it seems that java does not support or optimize the tail recursion very well (correct me if I am wrong). The recursion method still attempts to call itself 2147483647 times on the stack!
Fortunately we know any recursion can be replaced by a while/for loop, so to fix this problem is not difficult.
public int divide(int dividend, int divisor) {
int res = Integer.MAX_VALUE;
if (divisor != 0) {
res = (int) div(abs(dividend), abs(divisor), 0);
if (dividend > 0 ^ divisor > 0) {
res = 0 - res;
}
}
return res;
}
private long abs(final long x) {
return x < 0 ? 0 - x : x;
}
private long div(long x, final long y) {
long res = 0;
while(x >= y ){
x -= y;
res++;
}
return res;
}
The second solution can pass all the predefined unit tests, it will however take too long for the worse cases, on my PC it’s nearly 1.45 sec. So the problem is that the div() method above is not efficient enough, next we want to improve the div() method to make the algorithm faster. I considered to use bit operator to realize the double function:
public int divide(int dividend, int divisor) {
int res = Integer.MAX_VALUE;
if (divisor != 0) {
res = (int) div(abs(dividend), abs(divisor), 0);
// if dividend and divisor are not positive at the same time
if (dividend > 0 ^ divisor > 0) {
res = 0 - res;
}
}
return res;
}
private long abs(final long x) {
return x < 0 ? 0 - x : x;
}
private long div(long x, long y, int sum) {
long oy = y, res = sum; // keep the origial y and the old sum
sum = 1; // reinitialize sum
while (x >= y) {
if (x < y << 1) { // if x smaller than double y
return res + div(x - y, oy, sum);
} else {
y <<= 1; // double y
sum <<= 1; // double sum
}
}
return res;
}
this solution has passed all the unit tests, and the performance is very good. However it will not pass the OJ System without the condition below because of the overflow condition at the beginning. in java, -2147483648/-1 returns exactly -2147483648, but in the online judge system, it expects 2147483647 (MAX_INT). Thus I will not say this solution is wrong. If you just want to pass the LeetCode OJ System, then replace the 3. line “if (divisor != 0)” with the following code:
// just to satisfy the leetcode online judge system if (divisor != 0 && (dividend != Integer.MIN_VALUE || divisor != -1))
rekinyZ's Blog 