medium

Pow(x, n)

Compute x raised to the power n without repeatedly multiplying one step at a time.

1. Define the problem

Pow(x, n)

Implement pow(x, n), which calculates x raised to the power n (x ⁿ ). Use recursion with the fast-power trick: halve n each call instead of multiplying x by itself n times. The base case is n = 0, which returns 1. Otherwise recurse once on half of n, then square that result — if n is odd, multiply in one more x. If n is negative, compute pow(x, -n) and invert it.

Constraints

  • -100.0 < x < 100.0
  • -231 ≤ n ≤ 231 - 1
  • n is an integer

Example

Inputx = 2.0, n = 10
Output1024.0

Explanation 2¹⁰ = 1024.

2. Know the words first

In plain terms

Divide and conquer
Breaking a problem into a smaller version of itself, solving that smaller piece once, then combining its result to build the original answer — here, computing one half-power and squaring it instead of repeating the work twice.
3. Visualize the solution

Halve the exponent each call, square on the way back up

Halve the exponent each call, square on the way back up
Statuspow(2, 10)

n = 10 is even. Call pow(2, 5) and wait to square its result.

What happens in this step

helper(2, 10) calls helper(2, 5)

10 is even, so half = helper(2, floor(10/2)) = helper(2, 5). The result will just be half * half once that returns.
Step 1 of 9

Steps to visualize

  1. If n is negative, compute pow(x, -n) and invert the result at the end.
  2. Base case: n = 0 returns 1 — any number to the power 0 is 1.
  3. If n is even, recurse once on pow(x, n / 2) and square the result.
  4. If n is odd, recurse on pow(x, (n - 1) / 2), square it, and multiply by one more x.
  5. Each call waits on the stack for its single recursive call before it can square (and possibly multiply) the answer.
4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Halve the exponent each call, square on the way back up
Statuspow(2, 10)

n = 10 is even. Call pow(2, 5) and wait to square its result.

What happens in this step

helper(2, 10) calls helper(2, 5)

10 is even, so half = helper(2, floor(10/2)) = helper(2, 5). The result will just be half * half once that returns.
Step 1 of 9
5. Solution

Solution

solution.tsTypeScript
function myPow(x, n) {
  function helper(base, exp) {
    if (exp === 0) {
      return 1; // base case
    }
    const half = helper(base, Math.floor(exp / 2)); // recursive case
    if (exp % 2 === 0) {
      return half * half;
    }
    return half * half * base;
  }

  if (n < 0) {
    return 1 / helper(x, -n);
  }
  return helper(x, n);
}
Time
O(log n)
Space
O(log n)
6. Test cases

Test cases

InputExpectedCovers
x = 2.0, n = 101024.0example from the docstring
x = 2.0, n = -20.25negative exponent inverts the result
x = 2.0, n = 01.0base case, any base to the power 0 is 1
x = 2.0, n = 12.0one recursive call deep, odd exponent
x = -2.0, n = 3-8.0negative base with an odd exponent stays negative
x = 0.5, n = 20.25fractional base
x = 2.0, n = 201048576.0a deeper recursion, several halvings
x = 1.0, n = 21474836471.0base 1 at the upper bound of n, stays shallow thanks to halving

Keep reading