Power of X (Pow(x, n))

Difficulty: Medium

Problem

Write a function that computes x raised to the integer power n, without using a built-in power function. It has to work when n is negative too. Solve it using recursion.

Example

Input: x = 3.0, n = 4
Output: 81.0
Explanation: 3^4 = 3 × 3 × 3 × 3 = 81.0

Brute-force approach

This is a recursion-focused problem. We go directly to the recursive solution using the Leap of Faith approach.

Time complexity: - · Space complexity: -

Optimal approach

Key insight: If someone magically gives you x^(n/2), then x^n = (x^(n/2))². Trust the recursion, square the result!

Use the Leap of Faith recipe to build a recursive fast power solution. Trust that myPow(x, n/2) works, then square the result.

Steps

  1. Base case: if n == 0, return 1
  2. If n < 0, return 1 / myPow(x, -n)
  3. If n is even: half = myPow(x, n/2), return half × half
  4. If n is odd: return x × myPow(x, n-1)

Time complexity: O(log n) · Space complexity: O(log n)

Pseudocode

function myPow(x, n):
    if n == 0: return 1
    if n < 0: return 1 / myPow(x, -n)
    if n is even:
        half = myPow(x, n/2)
        return half * half
    else:
        return x * myPow(x, n-1)

Hints

  • What's the simplest power to compute? (Base case: n = 0)
  • If someone gives you x^(n/2), can you get x^n? (Leap of Faith!)
  • Handle odd n by reducing it: x^n = x × x^(n-1)

Complexity questions

What is the time complexity of recursive fast power?

O(log n). We halve the exponent at each step, giving log₂(n) levels of recursion, O(log n) total multiplications.

What is the space complexity of the recursive fast power approach?

O(log n). The recursion depth is O(log n), and each frame uses constant space, O(log n) total.

How many recursive calls does myPow(2, 10) make?

6. myPow(2,10) → myPow(2,5) → myPow(2,4) → myPow(2,2) → myPow(2,1) → myPow(2,0). That's 6 calls total (including the base case). Much better than 10!

Check your understanding of Power of X (Pow(x, n))

If someone magically gives you 2^5 = 32, how do you compute 2^10?

32 × 32 = 1024 (square it!). That's the Leap of Faith! If you TRUST that myPow(2, 5) = 32, then myPow(2, 10) = 32 × 32 = 1024. Just square the result!

How do we handle negative exponents like x^(-3)?

Return 1/(x^3). x^(-n) = 1/(x^n). So 2^(-3) = 1/(2^3) = 1/8 = 0.125. We convert it to a positive exponent problem first.

Why is this approach O(log n) instead of O(n)?

We halve the exponent at each step. Each recursive call halves the exponent (for even n). So the number of calls is log₂(n). For n=1,000,000,000 that's only ~30 calls!

Related problems

Keep practising