How do you solve Pow(x, n)?

Implement a recursive helper function that returns 1 if n is zero, returns 0 if x is zero, and otherwise recursively computes helper(x*x, n//2). If n is odd, multiply the result by x. The main function calls this helper with the absolute value of n and returns the result or its reciprocal depending on the sign of n.

Pow(x, n)

Q: What is the time complexity of Pow(x, n)?

O(log n). Each recursive call halves the exponent n, leading to a recursion depth of log n. Each call performs a constant number of multiplications.

Q: What pattern does Pow(x, n) use?

The Pattern: Divide and Conquer (Exponentiation by Squaring) The Heuristic: To compute powers efficiently, recursively reduce the exponent by half each step by squaring the base, and multiply by the base once more if the exponent is odd; this transforms O(n) multiplications into O(log n).

Medium Math & Geometry

Problem

Given a floating-point number x and an integer n, return x raised to the power n (i.e., x^n).

−100.0 < x < 100.0
−2³¹ ≤ n ≤ 2³¹ - 1

Example

Input: x = 2.0, n = 10

Output: 1024.0

A naive approach would multiply 2.0 by itself 10 times, resulting in 1024.0. However, this requires 10 multiplications. The recursive divide and conquer approach reduces the number of multiplications by repeatedly squaring the base and halving the exponent. For example, 2^10 = (2^5)^2. The recursion continues until the exponent reaches zero (base case), returning 1. The critical moment is when the exponent is odd, requiring an extra multiplication by the base to account for the leftover factor.

Approach

Straightforward Solution

A straightforward solution multiplies x by itself n times, resulting in O(n) time complexity, which is inefficient for large n.

Core Observation

Exponentiation can be expressed recursively as x^n = (x^2)^(n//2) when n is even, and x * (x^2)^(n//2) when n is odd. This reduces the problem size by half at each step, enabling logarithmic time complexity.

Path to Optimal

Preview

Recognizing that repeated multiplication can be optimized by squaring the base and halving the exponent leads to a divide and conquer approach. This reduces the number of multiplications from linear to logarithmic in n…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Implement a recursive helper function that returns 1 if n is zero, returns 0 if x is zero, and otherwise recursively computes helper(x*x, n//2). If n is odd, multiply the result by x…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(log n)

Each recursive call halves the exponent n, leading to a recursion depth of log n. Each call performs a constant number of multiplications.

Space

O(log n)

The recursion stack depth is proportional to log n due to halving the exponent at each step. No additional significant auxiliary space is used.

Pattern Spotlight

Divide and Conquer (Exponentiation by Squaring)

To compute powers efficiently, recursively reduce the exponent by half each step by squaring the base, and multiply by the base once more if the exponent is odd; this transforms O(n) multiplications into O(log n).

Solution

Python

1class Solution:
  def myPow(self, x: float, n: int) -> float:
      def helper(x, n):
          if x == 0: return 0
          if n == 0: return 1
6
          res = helper(x * x, n // 2)
          return x * res if n % 2 else res
9
      res = helper(x, abs(n))
      return res if n >= 0 else 1 / res

Step-by-Step Solution

Handle Negative and Zero Exponents with Recursive Helper

4if x == 0: return 0
5if n == 0: return 1
7res = helper(x * x, n // 2)

Objective

To correctly compute power for positive exponents and handle zero and zero-base edge cases.

Key Insight

The recursive helper function uses divide and conquer by squaring the base and halving the exponent, which reduces the problem size exponentially. It returns 1 when the exponent is zero, as any number to the zero power is 1, and returns 0 immediately if the base is zero, as zero to any positive power is zero. This base case handling prevents unnecessary recursion and ensures correctness.

Interview Quick-Check

Core Logic

The helper function recursively computes power by squaring the base and halving the exponent, returning 1 for exponent zero and 0 for base zero.

State & Boundaries

Base cases prevent infinite recursion and handle mathematical edge cases: x == 0 returns 0, n == 0 returns 1.

Common Pitfalls & Bugs

Failing to handle zero base or zero exponent correctly can lead to incorrect results or infinite recursion.

Combine Recursive Results and Handle Odd Exponents

To combine the recursive results by multiplying the squared base power and adjusting for odd exponents.

Adjust Final Result for Negative Exponents

To compute the final power value by handling negative exponents via reciprocal.

2 more steps with full analysis available on Pro.

Line Analysis

This solution has 4 Critical lines interviewers watch for.

Line 5 Critical

if n == 0: return 1

Return 1 if the exponent n is zero.

Any number raised to the zero power is 1, making this the essential base case for terminating recursion.

Line 8 Critical

return x * res if n % 2 else res

Multiply by x if n is odd, otherwise return the recursive result directly.

Multiplying by x when n is odd accounts for the lost factor due to integer division, ensuring the correctness of the exponentiation.

Line 7 Critical

res = helper(x * x, n // 2)

Recursively compute helper(x squared, n halved).

This line implements the divide and conquer step by reducing the problem size exponentially, enabling O(log n) time complexity.

Full line-by-line criticality + rationale for all 6 lines available on Pro.

Test Your Understanding

Why does the algorithm multiply by x only when the exponent n is odd?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Pow(x, n) from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Pow(x, n) drill

or drill a free problem

1	`class Solution:`
2	`def myPow(self, x: float, n: int) -> float:`
3	`def helper(x, n):`
4	`if x == 0: return 0`
5	`if n == 0: return 1`
6
7	`res = helper(x * x, n // 2)`
8	`return x * res if n % 2 else res`
9
10	`res = helper(x, abs(n))`
11	`return res if n >= 0 else 1 / res`