Python solution with detailed explanation


  • 0
    G

    Solution

    Pow(x, n) https://leetcode.com/problems/powx-n/

    Algorithm

    • x and n can be negative as well.
    • Use divide and conquer..
    class Solution(object):
        def myPow(self, x, n):
            """
            :type x: float
            :type n: int
            :rtype: float
            """
            neg = True if x < 0 and n%2 == 1 else False
            n_neg = True if n < 0 else False
            answer = self.helper_pow(abs(x), abs(n))
            answer = answer*-1 if neg else answer
            answer = 1.0/answer if n_neg else answer        
            return answer
        
        def helper_pow(self, x, n):
            if n == 0:
                return 1
            y = self.helper_pow(x, n//2) if n%2 == 0 else self.helper_pow(x, (n-1)//2)
            result = y*y if n%2 == 0 else x*y*y        
            return result
    

Log in to reply
 

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