Pow(x, n)

Examples

Input: x = 2.0, n = 10
Output: 1024.0

2 multiplied by itself 10 times.

Input: x = 2.1, n = 3
Output: 9.261

2.1 * 2.1 * 2.1 = 9.261.

Input: x = 2.0, n = -2
Output: 0.25

x^-2 means 1 / x^2 = 1 / 4 = 0.25.

Constraints

• -100 < x < 100

• -2^31 <= n <= 2^31 - 1

• x != 0, or n > 0

• n can be negative

Approach

The most direct approach multiplies x by itself n times in a loop. It's easy to reason about, but it does n multiplications, which is noticeably slow once n is large (say, in the billions).

A much faster approach notices that you don't need to redo all the multiplications for each power - if you already know x raised to n/2, you can square that single result to get x raised to n (adjusting by one extra factor of x when n is odd). Repeating that halving idea, the exponent shrinks by half at every step instead of by just one, cutting the number of multiplications down to roughly log2(n). A negative n is handled up front, by computing with 1/x and a positive exponent instead.

Solutions

Brute Force - Repeated Multiplication

For a negative exponent, first flip x to 1/x and make n positive. Then multiply x into a running result, once for every unit of n.

function myPow(x, n) {
  if (n < 0) {
    x = 1 / x;
    n = -n;
  }

  let result = 1;
  for (let i = 0; i < n; i++) {
    result *= x;
  }

  return result;
}

Time: O(n) · Space: O(1)

Optimal - Fast (Binary) Exponentiation

For a negative exponent, first flip x to 1/x and make n positive, same as before. Then compute the power recursively: find x^(n/2), square it, and multiply in one extra factor of x if n was odd. Each recursive call halves the exponent, instead of only reducing it by one.

function myPow(x, n) {
  if (n < 0) {
    x = 1 / x;
    n = -n;
  }

  return fastPow(x, n);
}

function fastPow(x, n) {
  if (n === 0) return 1;

  const half = fastPow(x, Math.floor(n / 2));
  const halfSquared = half * half;

  return n % 2 === 0 ? halfSquared : halfSquared * x;
}

Time: O(log n) · Space: O(log n), for the recursion stack