#50

Medium

LeetCode Problem Workspace

Pow(x, n)

Calculate x to the power n efficiently using recursion and exponentiation, handling negative powers and large inputs safely.

math recursion

Problem Statement

Implement a function pow(x, n) that calculates x raised to the power n (x^n). The function must handle negative exponents and large n efficiently while avoiding floating-point errors.

For example, pow(2.00000, 10) should return 1024.00000, pow(2.10000, 3) should return 9.26100, and pow(2.00000, -2) should return 0.25000. Constraints include -100.0 < x < 100.0, -2^31 <= n <= 2^31-1, n being an integer, and either x not zero or n > 0.

Examples

Example 1

Input: x = 2.00000, n = 10

Output: 1024.00000

Example details omitted.

Example 2

Input: x = 2.10000, n = 3

Output: 9.26100

Example details omitted.

Example 3

Input: x = 2.00000, n = -2

Output: 0.25000

2-2 = 1/22 = 1/4 = 0.25

Constraints

-100.0 < x < 100.0
-231 <= n <= 231-1
n is an integer.
Either x is not zero or n > 0.
-104 <= xn <= 104

Solution Approach

Recursive Exponentiation by Squaring

Use recursion to halve the exponent at each step. If n is negative, compute pow(x, -n) and return 1/result. Multiply intermediate results for even and odd exponents separately to maintain correctness.

Handle Negative Powers Carefully

Check if n is negative before recursion. Convert n to positive safely, considering integer overflow limits, then apply the recursive pattern. Return 1/result for the final output to handle negative exponents.

Optimize Base Cases and Multiplications

Define base cases for n = 0 and n = 1 to stop recursion early. Reduce redundant multiplications by reusing the result of pow(x, n//2) when n is even, ensuring logarithmic recursion depth.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(log n) due to halving the exponent at each recursive call. Space complexity is O(log n) from recursion stack usage.

What Interviewers Usually Probe

Recognizes negative exponent handling is required.
Uses recursion to optimize repeated multiplications.
Considers integer overflow and floating-point precision issues.

Common Pitfalls or Variants

Common pitfalls

Failing to handle n = INT_MIN correctly when negating.
Recomputing pow(x, n//2) multiple times instead of storing intermediate results.
Ignoring base cases for n = 0 or n = 1, causing unnecessary recursion.

Follow-up variants

Implement iterative version to reduce recursion stack usage.
Extend to handle fractional exponents with floating-point math.
Support modular exponentiation for large integer powers under modulo constraints.

FAQ

What is the main pattern used in Pow(x, n)?

The problem uses Math plus Recursion pattern, optimizing exponentiation by halving the exponent recursively.

How do I handle negative exponents in pow(x, n)?

Convert n to positive and return 1/pow(x, -n), carefully avoiding integer overflow for n = INT_MIN.

What is the time complexity of the recursive solution?

Time complexity is O(log n) since the exponent is halved at each recursive step.

Why should pow(x, n//2) results be reused?

Reusing avoids redundant calculations and ensures logarithmic recursion depth, preventing unnecessary multiplications.

What are the base cases in Pow(x, n)?

Base cases are n = 0 returning 1 and n = 1 returning x, which stop recursion safely.

terminal

Solution

Solution 1: Mathematics (Fast Powering)

The core idea of the fast powering algorithm is to decompose the exponent $n$ into the sum of $1$s on several binary bits, and then transform the $n$th power of $x$ into the product of several powers of $x$.

1

2

3

4

5

6

7

8

9

10

11

12

class Solution:
    def myPow(self, x: float, n: int) -> float:
        def qpow(a: float, n: int) -> float:
            ans = 1
            while n:
                if n & 1:
                    ans *= a
                a *= a
                n >>= 1
            return ans

        return qpow(x, n) if n >= 0 else 1 / qpow(x, -n)

Continue Practicing

#60 permutation sequence #2 add two numbers #224 basic calculator