# [LeetCode 29] Divide Two Integers

### Question

Divide two integers without using multiplication, division and mod operator.

### Stats

 Frequency 3 Diffficulty 4 Adjusted Difficulty 4 Time to use ----------

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

### Analysis

This question might be more difficult than you thought. So do not overlook it because of its seemingly simple description. First of all, please refer to [Fundamental] Java Bit Operation for information on bit operators.

And remember… overflow can happen, especially when you dealing with Integer.MAX_VALUE and Integer.MIN_VALUE.

### Solution

This solution is a while loop that keeps subtracting (divisor * (2 ^ n)) from dividend. You can find a good solution from this blog.

### code

``````public class Solution {
public int divide(int dividend, int divisor) {
int sign = 1;
long x = dividend;
long y = divisor;
if (x < 0) {
x = x * -1;
sign *= -1;
}
if (y < 0) {
y = y * -1;
sign *= -1;
}
return divide(sign, x, y);
}

private int divide(int sign, long x, long y) {
// both x and y are positive numbers
if (x < y) {
return 0;
}
long quotient = 0;
long partialQuotient;
long partialSubtract;
while (x >= y) {
// the idea is to subtract a certain times of x from y
// and save the remainder value back to x
partialQuotient = 1;
partialSubtract = y;
while ((partialSubtract << 1) <= x) {
partialQuotient <<= 1; // doubles quotient
partialSubtract <<= 1; // doubles subtraction
}
x -= partialSubtract;
quotient += partialQuotient;
}
long finalQuo = sign * quotient;
if (finalQuo < Integer.MIN_VALUE || finalQuo > Integer.MAX_VALUE) {
return Integer.MAX_VALUE;
} else {
return (int) finalQuo;
}
}
}
``````