#141 Medium Time O(log n) Space O(log n) Animated

Pow(x, n)

Implement pow(x, n), which calculates x raised to the power n.

LeetCode ↗

Approach: Divide and Conquer (Fast Power)

Click play to start

Step 0 / 0

Press play to start the visualization.

1×

Description

Implement pow(x, n), which calculates x raised to the power n.

Constraints

Time Complexity: O(log n)
Space Complexity: O(log n)

Solution — Divide and Conquer (Fast Power)

O(log n) O(log n)

def myPow(x, n):
    def helper(x, n):
        if x == 0: return 0
        if n == 0: return 1
        
        res = helper(x, n // 2)
        res = res * res
        return x * res if n % 2 else res
        
    res = helper(x, abs(n))
    return res if n >= 0 else 1 / res

Plus One

Multiply Strings

Pow(x, n)

Steps

Description

Constraints

Tags

Solution — Divide and Conquer (Fast Power)