[LeetCode] 50. Pow(x, n)

Table of Contents

Description

Implement the function pow(x, n), which calculates x raised to the power n (i.e., $x^n$).

Example 1:
Input: x = 2.00000, n = 10
Output: 1024.00000

Example 2:
Input: x = 2.10000, n = 3
Output: 9.26100

Example 3:
Input: x = 2.00000, n = -2
Output: 0.25000
Explanation: $2^{-2} = 1 / (2^2) = 0.25$

Approach

We can use Exponentiation by Squaring to compute $x^n$ efficiently. Instead of multiplying $x$ by itself $n$ times, we recursively break down the problem:

• If $n$ is even, we can write:

  $$x^n = (x^{n/2})^2$$

  For example, $x^4 = (x^2)^2$.

• If $n$ is odd, we use:

  $$x^n = x \times x^{n-1}$$

  For example, $x^5 = x \times x^4$.

• If $n < 0$, we compute the reciprocal:

  $$x^n = 1 / x^{-n}$$

This recursive approach reduces the number of multiplications and handles both positive and negative exponents. By halving the exponent at each step, the algorithm achieves logarithmic time complexity.

Solution

/**
 * @param {number} x
 * @param {number} n
 * @return {number}
 */
var myPow = function (x, n) {
  // Base case: any number to the power 0 is 1
  if (n === 0) return 1;

  // Base case: power of 1 returns the base itself
  if (n === 1) return x;

  // Base case: power of -1 returns the reciprocal of the base
  if (n === -1) return 1 / x;

  const currentProduct = n % 2 ? x : 1;

  // Recursive call: square the base and halve the exponent (floor division)
  // Multiply by currentProduct if n is odd
  return currentProduct * myPow(x * x, Math.floor(n / 2)) || 0;
};

Complexity Analysis

Time Complexity

The time complexity is $O(\log |n|)$, because each recursive (or iterative) step halves the exponent, resulting in logarithmic growth with respect to $|n|$.

Space Complexity

The space complexity is $O(\log |n|)$ for the recursive approach, due to the call stack depth. If implemented iteratively, the space complexity is $O(1)$.