MediumRecursionMathDivide and Conquer

Pow(x, n)

2 approaches, code in every language

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 see the solution

You get 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

After the pattern

Now solve one you haven't seen.

Zoom Stage Multiplier is our own problem on the technique behind Pow(x, n): a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free

Pow(x, n)

Problem description

Example 1

Example 2

Constraints

Create a free account to see the solution

Now solve one you haven't seen.