MediumRecursionMathDivide and Conquer

Pow(x, n)

2 approaches, code in all languages

Implement exponentiation. Given a real base x and an integer exponent n, return x raised to the power n, written x^n.

The exponent can be zero or negative. A negative exponent means the reciprocal of the corresponding positive power, so x^(-k) is 1 divided by x^k.

Example 1

Input: x = 2.00000, n = 10

Output: 1024.00000

Example 2

Input: x = 2.00000, n = -2

Output: 0.25000

2^(-2) = 1 / 2^2 = 1 / 4 = 0.25.

Constraints

−100.0 < x < 100.0
−2^31 ≤ n ≤ 2^31 − 1 and n is an integer
Either x is non-zero or n is greater than 0
The final result stays within the range [−10^4, 10^4]

Recursive fast exponentiation

Halve the exponent each call: square the half-power and multiply by the base once more when the exponent is odd.

Loading animation…

Intuition

Raising to a power can be split in half, since x^n equals the square of x^(n/2), with one extra factor of x whenever n is odd. Each recursive level halves the exponent, so only about log(n) multiplications are needed instead of n of them.

Algorithm walkthrough

1Handle a negative exponent by inverting the base and negating the exponent, using a wide integer so that the most negative value does not overflow.
2Recurse to compute half = power(base, exp / 2).
3If the exponent is even, the answer is half * half.
4If the exponent is odd, the answer is half * half * base.
5The recursion stops when the exponent reaches 0, returning 1.

Implementation

class Solution:
    def myPow(self, x: float, n: int) -> float:
        def power(base: float, exp: int) -> float:
            if exp == 0:
                return 1.0
            half = power(base, exp // 2)
            if exp % 2 == 0:
                return half * half
            return half * half * base

        if n < 0:
            return power(1 / x, -n)
        return power(x, n)

Time

O(log n)

Space

O(log n)

Iterative binary exponentiation

Fold the set bits of the exponent into the result while repeatedly squaring the base.

Intuition

The binary form of the exponent tells us exactly which squared powers of the base to combine. By squaring the base at every step and multiplying it into the result whenever the current lowest bit is set, we assemble x^n from only log(n) building blocks.

Algorithm walkthrough

1Normalize a negative exponent by inverting the base and taking the absolute value with a wide integer.
2Start result at 1 and let the base track x, x^2, x^4, and so on.
3While the exponent is positive, if its lowest bit is set, multiply the current base power into result.
4Square the base and shift the exponent one bit to the right.
5Return result once the exponent reaches 0.

Implementation

class Solution:
    def myPow(self, x: float, n: int) -> float:
        if n < 0:
            x = 1 / x
            n = -n
        result = 1.0
        while n > 0:
            if n & 1:
                result *= x
            x *= x
            n >>= 1
        return result

Time

O(log n)

Space

O(1)

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in

Back to Recursion

You've got the patterns

Patterns get you through the screen. Shipping gets you hired.

FDE Coach is a cohort-based program in frontend, backend, AWS, and AI where you build real products and get referred to 200+ hiring partners. The free live workshop is the fastest way to see how we teach.

Join the free workshop Explore the program

750+ engineers trained · frontend, backend, AWS & AI