Clean Java solution with some comment.

• ``````public int divide(int dividend, int divisor) {
//Reduce the problem to positive long integer to make it easier.
//Use long to avoid integer overflow cases.
int sign = 1;
if ((dividend > 0 && divisor < 0) || (dividend < 0 && divisor > 0))
sign = -1;
long ldividend = Math.abs((long) dividend);
long ldivisor = Math.abs((long) divisor);

//Take care the edge cases.
if (ldivisor == 0) return Integer.MAX_VALUE;
if ((ldividend == 0) || (ldividend < ldivisor))	return 0;

long lans = ldivide(ldividend, ldivisor);

int ans;
if (lans > Integer.MAX_VALUE){ //Handle overflow.
ans = (sign == 1)? Integer.MAX_VALUE : Integer.MIN_VALUE;
} else {
ans = (int) (sign * lans);
}
return ans;
}

private long ldivide(long ldividend, long ldivisor) {
// Recursion exit condition
if (ldividend < ldivisor) return 0;

//  Find the largest multiple so that (divisor * multiple <= dividend),
//  whereas we are moving with stride 1, 2, 4, 8, 16...2^n for performance reason.
//  Think this as a binary search.
long sum = ldivisor;
long multiple = 1;
while ((sum+sum) <= ldividend) {
sum += sum;
multiple += multiple;
}
//Look for additional value for the multiple from the reminder (dividend - sum) recursively.
return multiple + ldivide(ldividend - sum, ldivisor);
}``````

• what is the run time of this algorithm?

• good idea, but still TLE

• Nice explanation with good self-descriptive identifiers. This solution shows that every number can be represented as sum of powers of 2 which is somewhat similar to how binary search works .
Also , no need to return Integer.MIN_VALUE since problem statement says return MAX_INT in case of overflow.

• In java, Integer.MAX_VALUE is a built-in static parameter representing 2^31-1. Problem asks you to return max integer value, describing in a programming language way of saying 'MAXINT', MAXINT is not a instance variable which has already been put in Solution Class so returning MAXINT will cause compile error.

• By MAXINT , I meant value 2^31-1 in general.
Yes , it will be Integer.MAX_VALUE in case of Java.

• Nice solution. Here is my shorter and easier to understand code.

Hint:

1. The divisor will never be 0.

2. Make the divisor as big as possible.

3. long to int, narrow down the range and then convert.

public class Solution {
public int divide(int dividend, int divisor) {
if (dividend == 0) {
return 0;
}
boolean neg = (dividend < 0) ^ (divisor < 0);
long m = Math.abs((long)dividend), n = Math.abs((long)divisor);
long result = 0;
while (m >= n) {
int shift = 0;
while (m > (n << shift + 1)) {
shift++;
}
m -= n << shift;
result += (1 << shift);
}
result = (neg) ? ~(result - 1) : result;
result = Math.min(Integer.MAX_VALUE, result);
result = Math.max(Integer.MIN_VALUE, result);
return (int)result;
}
}

• thanks for sharing! we are on the same track, yet i think my code is shorter and clearer:

``````/*
-- possible overflow: Integer.MIN_VALUE / (-1); anything / 0.
*/
public class Solution {
public int divide(int dividend, int divisor) {
if (divisor == 0 || dividend == Integer.MIN_VALUE && divisor == -1) return Integer.MAX_VALUE;
int sign = (dividend ^ divisor) >> 31;
int quotient = divideHelper(Math.abs(Long.valueOf(dividend)), Math.abs(Long.valueOf(divisor)));
return sign == 0 ? quotient : -quotient;
}

private int divideHelper(long top, long bot) {
if (top < bot) return 0;
long cur = bot;
int count = 1;
while (cur <= (top >>> 2)) {
cur <<= 1;
count <<= 1;
}
count += divideHelper(top - cur, bot);
return count;
}
}
``````

• in which context that result could overflow

• Keep substracting divisor and double it each time. Whenever you overshoot and divisor goes more than dividend, go back to previous value, and try again.

``````public int divide(int a, int b) {
if(a==Integer.MIN_VALUE){
if(b==-1) return Integer.MAX_VALUE;
}

long x = a < 0 ? -(long)a : (long)a;
long y = b < 0 ? -(long)b : (long)b;

int res = recurse(x, y, 1);
if(a < 0 && b < 0) return res;
if(a < 0 || b < 0) return -res;
return res;
}

public int recurse(long x, long y, int count) {
if(x <= 0 || count==0) return 0;
if(y > x) return recurse(x, y >>> 1, count >>> 1); //overshot, so divide and try again.
else return recurse(x-y, y+y, count+count)+count;
}``````

• why result = (neg) ? ~(result - 1) : result;?
I do not understand how it makes result to take the negative result value.

• This post is deleted!

• @xia9 for example, Integer.MIN_VALUE / -1 will cause a overflow.

• public class Solution {
public static int divide(int dividend, int divisor) {
if(divisor==0||dividend==Integer.MIN_VALUE&&divisor==-1) return Integer.MAX_VALUE;
if(divisor==1) return dividend;
int sign=((dividend>0)^(divisor>0))?-1:1;
long did=Math.abs((long)dividend);
long div=Math.abs((long)divisor);
int res=0;
while(did>=div){
long tmp=div;
int mutiple=1;
while(did>=(tmp<<1)){
tmp<<=1;
mutiple<<=1;
}
did-=tmp;
res+=mutiple;
}
return sign==-1?-res:res;
}
}

• your code is nicely structured and easy to understand! Thanks for your solution!

• anyone know why this method have to use "long" type
I understand the other method by using bit operation.
However, I don't think it is necessary to use long in this recursion method. Since inputs are valid. the "lans" should never be larger than dividend

• @sixgod Suppose you use Math.abs() for Integer.MIN_VALUE. The absolute value of Integer.MIN_VALUE would overflow if not use long type.

• @jaqenhgar Hello , I find out that in your solution when I change `if(x <= 0 || count==0) return 0;`
into `if(x == 0 || count==0) return 0;`,it also works well and even faster. So is there any reason why you choose the first one?

• Thank you @jinwu for your idea. I think your implementation can be simplified.
Your idea is mainly based on long division.
Here is the simplified implementation based on long division:

``````public int divide(int dividend, int divisor) {
if (divisor == 0 || (dividend == Integer.MIN_VALUE && divisor == -1)) return Integer.MAX_VALUE;
// idea similar to "long division"
int sign = (dividend > 0) ^ (divisor > 0) ? -1 : 1;// XOR to determine same sign?
long ldividend = Math.abs((long)dividend);
long ldivisor = Math.abs((long)divisor);
long multiple = 1;
long ans = 0;
// STEP 1: shift "divisor" to the most siginificant bit
while ((ldivisor << 1) <= ldividend) {
multiple <<= 1;
ldivisor <<= 1;
}
// STEP 2: shift right to perform "long division"
while (multiple > 0) {
if (ldividend >= ldivisor) {
ldividend -= ldivisor;
ans += multiple;
}
multiple >>= 1;
ldivisor >>= 1;
}
return sign == 1 ? (int)ans : (int)-ans;
}
``````

• This post is deleted!

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