O(log(n))in c++, timelimit exceed


  • 0
    N
    class Solution {
        private:
            bool pos=0;
    public:
        int divide(int dividend, int divisor) {
    
           
           
            if(dividend<0)
                pos=~pos;                       //pos =1 result should be a negative integer
            if(divisor<0)
                pos=~pos;
                
            if(pos)
                return -PositiveDivide((long int)dividend,(long int)divisor);
            else
                return PositiveDivide((long int)dividend,(long int)divisor);        //
     
            
            
        }
        
        int PositiveDivide(long int dividend, long int divisor){
            dividend=abs(dividend);                                 //deal with positive value
            divisor=abs(divisor);                       
            
            if(dividend<divisor)
                return 0;
             
             int result=0;
            int temp=divisor;                               
        
            while(dividend>=temp){
                int k=1;
                while(dividend-temp>=temp){                             //shift temp until temp<1/2 dividend
                    temp=temp<<1;                                       
                    k=k<<1;
                
                }
                dividend-=temp;                             
                temp=divisor;
                result+=k;
            
            }
            
            
            return result;
            
        }
    };

  • 0
    S

    Pay attention to "Writing code? Select all code block then click on the {} button to preserve code formatting.” above text editor.


  • 0
    R

    my guess for TLE is that it could be done in constant time..


Log in to reply
 

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