#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 ↗

Tutor Mode Build the mental model before you memorize the code.

1 Predict
2 Trace
3 Explain
4 Implement

Pattern Direct simulation with preserved structure

Name the mathematical relationship first, then apply it consistently to every position or digit.

Approach: Divide and Conquer (Fast Power)

Click play to start

Step 0 / 0

Press play to start the visualization.

1×

Core Insight

Name the mathematical relationship first, then apply it consistently to every position or digit.

Common Pitfall

Write down index and boundary conditions before mutating an in-place structure.

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)

TimeO(log n) SpaceO(log n)

Implementation Plan

Translate the invariant into these small, testable moves.

Identify the formula or transformation.
Set boundary conditions.
Process each required position.
Return the transformed result.

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)