Share my accepted python solution, (russian


  • 6
    L

    I guess, this is easy to understand, the time complex is O(log(n)), this is a fast implementation.

    class Solution:
    # @param x, a float
    # @param n, a integer
    # @return a float
    def pow(self, x, n):
        if(n==0):
            return 1;
        elif(n==1):
            return x;
        if(n<0):
            return self.pow(1/x,-n);
        else:
            if(n%2==0):
                return self.pow(x*x,n/2);
            else:
                return self.pow(x*x,(n-1)/2)*x;

  • 0
    P

    Thank you for sharing. The solution shared can pass both of my local test and LeetCode online test.

    The following is my solution. However, it cannot pass leetcode online test. It failed at the case of (8.88023, 3). It's a Runtime Error. And I have no idea why. I will appreciate if someone can share some ideas so I can figure it out.

    {

    def power(self, x, n):
        if x == 0:
            return 0
        if n == 0:
            return 1
        
        result = self.power(x, n//2)
        if n % 2 == 0:
            return result * result
        else:
            return result * result * x
    
    def pow(self, x, n):
        if n > 0:
            return self.power(x, n)
        else:
            return 1/self.power(x, n)
    

    }

    I also found a solution somewhere over the web. Please see the following. It can pass leetcode test cases. However, it cannot pass my local test case. The test case is simply the same as the above (8.88023, 3).

    {

    def pow(self, x, n):
        if n == 0:
            return 1.0
        elif n < 0:
            return 1 / self.pow(x, -n)
        elif n % 2:
            return self.pow(x*x,n/2)*x
        else:
            return self.pow(x*x,n/2)
    

    }


  • 0
    L

    seems leetcode will treat 0.5 as 1, but you local will treat 0.5 as 0.

    I solve your question, by

    self.power(x, int((n+0.9)/2))
    

    However, your solution still has some issue, please refine them.

    for the code next, you should use int()

    def pow2(self, x, n):
            if n == 0:
                return 1.0
            elif n < 0:
                return 1 / self.pow2(x, -n)
            elif n % 2:
                return self.pow2(x*x,int(n/2))*x
            else:
                return self.pow2(x*x,int(n/2))
    

  • 0
    P

    Thank you very much for your help.

    I think the "result = self.power(x, n//2)" is supposed to work.

    Then I simply changed
    {
    return 1/self.power(x, -n)
    }
    from
    {
    return 1/self.power(x, n)
    }

    then things all worked. I am happy about that. But it's weird ... I still don't understand why the negative one matters ...

    And for the code next, I simply use n//2 instead of n/2. Then things are working.


Log in to reply
 

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