Pow(x, n)

Try It Yourself

Use the editor below to calculate x raised to an integer power without built-in exponentiation. Reduce the exponent toward zero on every recursive call.

Submit your implementation when it passes the examples. Handle negative exponents, zero, and negative base values.

Pow(x, n)

mediumRecursion · Divide and Conquer30 minLC 50

Problem

Implement a function that raises x to the integer power n.

Handle zero and negative exponents without using the language's built-in exponentiation operation.

Example 1:

Input: x = 2, n = 10

Output: 1024

Example 2:

Input: x = 2, n = -2

Output: 0.25

Constraints

-2³¹ ≤ n ≤ 2³¹ - 1
Do not use Math.pow, **, or pow.

0 attempts

Solution

A zero exponent is the base case and returns 1. For larger exponents, recursively calculate the result for half the exponent and square that result.

An odd exponent needs one additional multiplication by the base. A negative exponent is handled by calculating the positive power and taking its reciprocal.

function myPow(x, n) {
  function power(exponent) {
    if (exponent === 0) return 1;

    const half = power(Math.floor(exponent / 2));
    const squared = half * half;

    return exponent % 2 === 0 ? squared : squared * x;
  }

  return n < 0 ? 1 / power(-n) : power(n);
}

Big O notation

Measure	Complexity	Explanation
Time	`O(log n)`	Each recursive call halves the absolute exponent.
Auxiliary space	`O(log n)`	The recursive call stack has one frame per halving step.