Why exceed time limit? I think mine is O(logn) as well


  • 0
    B

    public double myPow(double x, int n) {

        if(n < 0){
            n = -n;
            x = 1 / x;
        }
        if(n == 0) return 1;
        double ret = x;
        int tmp = 1;
        while(2 * tmp <= n){
            tmp += tmp;
            ret *= ret;
        }
        
       return ret * myPow(x, n - tmp);
        
    }
    

    Failed at x = 0.00001, k = 2147483647
    Anyone knows why? Thanks!


  • 0

    That number is the largest possible int value, so some_int <= 2147483647 will always be true. You built an infinite loop.


  • 0
    H

    Also have you considered that after a few iterations of multiplying by 0.00001 you will have a value of zero at which point you can probably stop with the multiplying...


  • 0
    B

    Thank you so much!


  • 0
    Q

    I think the time complexity of your algorithm is (logn)^2.
    It seems for the k-th bit, your iteration takes O(k) time.


Log in to reply
 

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