LeetEye LeetEye
Medium Math & Geometry ~5 min

Pow(x, n)

math-and-geometry powx-n

Problem

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

Examples

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
2^-2 = 1/2^2 = 1/4 = 0.25
Key Insight

Binary exponentiation: x^n = (x^(n/2))^2 for even n, x * x^(n-1) for odd n.

Binary exponentiation: halve exponent each step. Even n: (x²)^(n/2). Odd n: x * (x²)^((n-1)/2). O(log n) multiplications.

How to Approach This Problem

Pattern Recognition: When you see keywords like pow(x, n) math-and-geometry, think Math & Geometry.

Step-by-Step Reasoning

1 Computing x * x * ... * x (n times) is:
Answer: O(n)
n multiplications for x^n. Too slow for large n.
2 x^10 can be computed as:
Answer: All of above
All are mathematically equivalent. (x^5)² uses fewer multiplications.
3 For even n, x^n = ?
Answer: (x^(n/2))²
Halves the problem size immediately.
4 For odd n, x^n = ?
Answer: A or C
Make it even by extracting one x, then apply even rule.
5 For negative n, x^n = ?
Answer: 1/x^n
x^(-n) = 1/(x^n). Compute positive power, take reciprocal.

Solution

def myPow(x: float, n: int) -> float:
    if n < 0:
        x = 1 / x
        n = -n
    
    result = 1
    while n > 0:
        if n % 2 == 1:  # Odd
            result *= x
        x *= x
        n //= 2
    
    return result

Complexity Analysis

Time O(log n)
Space O(log n)

Master This Pattern

Build intuition with interactive MCQs. Practice Math & Geometry problems in the LeetEye app.

Download LeetEye Free
Practice in LeetEye