# A strange error: MLE??? i Just use a map and vector, which is constant space; the code is passed in IDE

• //first calculate divisor, 2 * divisor, 4 * divisor, 8 * divisor......until 2 ^ n * divisor < dividend and 2 ^ ( n+1 ) * divisor > dividend

//map< int, int > flag store the responding 1, 2, 4, 8, .... 2 ^ n

//vector< int > tmp store the divisor, 2 * divisor, 4 * divisor...........

//sum is the result;

//we use dividend minus the nearest divisor in tmp, and add the respoding flag to sum

// until the dividend is less than tmp[0], which is the least divisor

//return the sum

``````    class Solution {
public:
int divide(int dividend, int divisor) {
int i = 1, sum = 0;
map<int, int> flag;
vector<int> tmp;

flag[divisor] = i;
tmp.push_back(divisor);
while(divisor < dividend)// map<int, int> flag store the 2^n * divisor
{
divisor += divisor;
i += i;
flag[divisor] = i;
tmp.push_back(divisor);
}

int size = tmp.size() - 1;
while(dividend >= tmp[0])
{
for(i = size; i >=0 ; i--)
{
if(tmp[i] <= dividend)
break;
}
sum += flag[tmp[i]];//
dividend -= tmp[i];
size -= 1;//it must be begin from the size - 1 every time,
}

return sum;
}
};``````

• I think you have to consider the case where `divisor` is negative or `dividend` is negative

• I modify my code as follow to support the negative situation, but still MLE. it's impossible to pass no cases.

``````   class Solution {
public:
int divide(int dividend, int divisor) {
int i = 1, sum = 0;
map<int, int> flag;
vector<int> tmp;
int mark;
if(divisor < 0 && dividend < 0)
{
divisor = -divisor;
dividend = -dividend;
mark = 1;
}
else if(divisor < 0 && dividend > 0)
{
divisor = -divisor;
mark = 0;
}
else if(divisor > 0 && dividend < 0)
{
dividend = -dividend;
mark = 0;
}
else if(divisor > 0 && dividend > 0)
mark = 1;
else
return 0;

flag[divisor] = i;
tmp.push_back(divisor);
while(divisor < dividend)
{
divisor += divisor;
i += i;
flag[divisor] = i;
tmp.push_back(divisor);
}

int size = tmp.size() - 1;
while(dividend >= tmp[0])
{
for(i = size; i >=0 ; i--)
{
if(tmp[i] <= dividend)
break;
}
sum += flag[tmp[i]];//??
dividend -= tmp[i];
size -= 1;
}
if(mark)
return sum;
else
return -sum;
}
``````

};

• There is no need to use `map` or `vector`

Just need to take care of the case where `dividend` or `divisor` could be `INT_MIN`

``````class Solution {
public:
int divide(int dividend, int divisor) {
if(dividend == divisor)
return 1;
if(divisor == -2147483648) return 0;
if(dividend == -2147483648) {
if(divisor > 0) {
dividend += divisor;
} else {
dividend -= divisor;
}
}
int i = 1, sum = 0;
int tmp[33];
int tmpsize = 0;
int flag[33];
int flagsize = 0;
int mark;
if(divisor < 0 && dividend < 0) {
divisor = -divisor;
dividend = -dividend;
mark = 1;
} else if(divisor < 0 && dividend > 0) {
divisor = -divisor;
mark = 0;
} else if(divisor > 0 && dividend < 0) {
dividend = -dividend;
mark = 0;
} else if(divisor > 0 && dividend > 0)
mark = 1;
else return 0;

flag[flagsize++] = i;
tmp[tmpsize++] = divisor;
while(divisor < dividend)
{
divisor += divisor;
i += i;
if(divisor<=0) break;
flag[flagsize++] = i;
tmp[tmpsize++] = divisor;
}

int size = tmpsize - 1;
while(dividend >= tmp[0])
{
for(i = size; i >=0 ; i--)
{
if(tmp[i] <= dividend)
break;
}
sum += flag[i];//??
dividend -= tmp[i];
size = i;
}
if(mark)
else
}
};``````

``````#include <limits.h>
class Solution {
private:
/* the higest bit of 'x' is 0 and x != 0 */
public:
int nlz(unsigned int x) {
int n = 0;
if ( (x >> 16) == 0 ) { n += 16; x <<= 16; }
if ( (x >> 24) == 0 ) { n +=  8; x <<=  8; }
if ( (x >> 28) == 0 ) { n +=  4; x <<=  4; }
if ( (x >> 30) == 0 ) { n +=  2; x <<=  2; }
n = n - (x >> 31);
return n;
}
public:
int divide(int dividend, int divisor) {
bool sign = (dividend ^ divisor) & 0x80000000;
if ( divisor == 0 )
return sign ? INT_MIN : INT_MAX;
else if ( divisor == INT_MIN )
return dividend == INT_MIN ? 1 : 0;
else if ( divisor == INT_MAX )
return dividend <= INT_MIN + 1 ? -1 :
dividend == INT_MAX ? 1 : 0;
else if ( divisor == 1 ) return dividend;
else if ( divisor == -1 )
return dividend == INT_MIN ? INT_MAX : -dividend;

if ( divisor < 0 ) divisor = -divisor;
int d = 0;
if ( dividend == INT_MIN ) {
dividend += divisor;
d ++;
//			fprintf(stderr, "d = %d\n", d);
}

int res = 0;
if ( dividend < 0 ) dividend = -dividend;
//		fprintf(stderr, "dividend=%d, divisor=%d\n", dividend, divisor);
int  divisor_nlz = nlz(divisor);
int dividend_nlz = nlz(dividend);
//		fprintf(stderr, "dividend_nlz=%d, divisor_nlz=%d\n", dividend_nlz, divisor_nlz);
for (int i = divisor_nlz - dividend_nlz; i >= 0; i --) {
fprintf(stderr, "i=%d ", i);
fprintf(stderr, "d: %d - %d\n", dividend, (divisor << i));
if ( dividend - (divisor << i) >= 0 ) {
res |= 1 << i;
dividend -= divisor << i;
}
}
res += d;
//		fprintf(stderr, "res=%d, d=%d\n", res, d);
return sign ? -res : res;
}
};
``````

• My algorithm includes two part, as you see. The first part is dealing with boardary cases, like max, min and 0, and convert the two number to positives. The second part is divide the two positive number, by using left shift and sub.

• ``````public class Solution {
public int divide(int dividend, int divisor) {
if(divisor==1) return dividend;
if(divisor==0) return (dividend>0?Integer.MAX_VALUE:Integer.MIN_VALUE);
if(divisor==Integer.MAX_VALUE){
if(dividend==Integer.MAX_VALUE) return 1;
if(dividend==Integer.MIN_VALUE) return -1;
else return 0;
}
if(divisor==Integer.MIN_VALUE){
if(dividend==Integer.MIN_VALUE) return 1;
else return 0;
}
int result=0;
boolean negRes=((dividend>0&&divisor<0)||(dividend<0&&divisor>0))?true:false;
divisor=divisor>0?divisor:-divisor;

if(dividend==Integer.MIN_VALUE) {
dividend+=divisor;
dividend=-dividend;
result=1;
}
dividend=dividend>0?dividend:-dividend;
if(dividend<divisor) return negRes?-result:result;
while(dividend>=divisor){
int tmp=divisor;
int tmp2=1;
while(largeThan2xTheSecondNumber(dividend,tmp)){
tmp2=tmp2<<1;
tmp=tmp+tmp;//tmp*=2;
}
dividend-=tmp;
result+=tmp2;
}
return negRes?-result:result;
}

private boolean largeThan2xTheSecondNumber(int a,int b){
//true if a>2*b
if(a<b) return false;
if(a-b>b) return true;
return false;
}
}
``````

Basic Idea:

1. if(divisor==1) return dividend;
2. if(divisor==0) return (dividend>0?Integer.MAX_VALUE:Integer.MIN_VALUE);
3. divisor is Integer.MAX_VALUE or Integer.MIN_VALUE; return 1,-1 or 0;
4. other input
first do dividend=abs(dividend) divisor=abs(divisor).
notice that abs(Integer.MIN_VALUE)==abs(Integer.MIN_VALUE) itself because Integer.MIN_VALUE is -2147483648 Integer.MAX_VALUE is 2147483647 we can not express 2147483648

so if dividend== Integer.MIN_VALUE we can do dividend+=abs(divisor) and then do abs(dividend), also add extra one to the final result.

after those works, we can discuss how to do division.

let say 110/10 =11

11=8+2+1 (1011)
we can simulate this feature as the following code.

``````while(dividend>=divisor){
int tmp=divisor;
int tmp2=1;
while(largeThan2xTheSecondNumber(dividend,tmp)){
tmp2=tmp2<<1;
tmp=tmp+tmp;//tmp*=2;
}
dividend-=tmp;
result+=tmp2;
}

/*
private boolean largeThan2xTheSecondNumber(int a,int b){
//true if a>2*b
if(a<b) return false;
if(a-b>b) return true;
return false;
}*/
``````

• The time complexity of your solution is O(dividend/divisor). Depending on the specific values of dividend and divisor, a simple binary search in interval [1, dividend] ( time complexity O(log(dividend)) might be better.

• I used a similar algorithm which still gets TLE

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