loading

50. Pow(x, n) — Step-by-Step Visualization

mediumLeetCode #50MathRecursion

Implement `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 = 1/4 = 0.25`

Algorithm Pattern

Binary Exponentiation / Fast Power

Key Idea

A naive linear approach (multiplying `x` n times) is O(n), but we can do it in O(log n) by squaring the base at each step. If `n` is even, `x^n = (x^2)^(n/2)`. If `n` is odd, `x^n = x * (x^2)^(n/2)`.

Step-by-Step Approach

  1. Handle negative exponents by setting `x = 1/x` and `n = -n`.
  2. Initialize `res = 1` and `current_x = x`.
  3. Iterate while `n > 0`:
  4. 1. If `n` is odd (`n % 2 == 1`), multiply `res` by `current_x`.
  5. 2. Square the base: `current_x = current_x * current_x`.
  6. 3. Half the exponent: `n = n // 2`.
  7. Return the final `res`.

Common Gotchas

  • Negative exponents must be handled first.
  • For `n = -2^31`, simply negating `n` can cause overflow in some languages, though JavaScript handles this easily with its Number type.

Related Problems

← All problems