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


  • 0
    W

    //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;
        }
    };

  • 0
    P

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


  • 0
    W

    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;
    }
    

    };


  • 0
    P

    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;
            int additional = 0;
            if(dividend == -2147483648) {
                if(divisor > 0) {
                    dividend += divisor;
                    additional = -1;
                } else {
                    dividend -= divisor;
                    additional = 1;
                }
            }
            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)
                return sum+additional;
            else
                return -sum+additional;
        }
    };

  • 0
    U

    Hope this can help you.

    #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;
        }
    };
    

  • 0
    S

    Could you please describe your algorithm in some words? And add comment in your code?


  • 0
    U

    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.


  • 0
    Y
    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;
    }*/
    

  • 0
    L

    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.


  • 0
    M

    I used a similar algorithm which still gets TLE


Log in to reply
 

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