Why my O(logn) solution get TLE?


  • 0
    D

    It's already O(logn) but why I still get TLE?

        int divide(int dividend, int divisor) {
        if (dividend == 0 || divisor == 0) return 0;
        
        bool isNegative = false;
        long long dividend2 = dividend;
        long long divisor2 = divisor;
        
        if (dividend2 < 0)
        {
            dividend2 = -dividend2;
            isNegative = !isNegative;
        }
        
        if (divisor2 < 0)
        {
            divisor2 = -divisor2;
            isNegative = !isNegative;
        }
        
        long long ret = 0;
        long long shift = 1;
        
        while (dividend2 >= (divisor2 << shift))
        {
            shift <<= 1;
        }
        
        while (dividend2 >= divisor2)
        {
            if (dividend2 >= (divisor2 << shift))
            {
                dividend2 -= (divisor2 << shift);
                ret += shift;
            }
            
            shift >>= 1;
        }
        
        if (isNegative)
        {
            ret = -ret;
        }
        
        return (int)ret;
    }

  • 0
    H

    error is here :

    while (dividend2 >= (divisor2 << shift))
        {
            shift <<= 1;
        }
    

    should be

    int i = 0
    while (dividend2 >= (divisor2 << i))
        {
            shift <<= i;
        }
    

    The following should be revised also

        if (dividend2 >= (divisor2 << shift))
        {
            dividend2 -= (divisor2 << shift);
            ret += shift;
        }
    

Log in to reply
 

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