Pow(x, n) Solution

Problem

Implement the function that raises a floating-point number x to an integer power n, including negative exponents. A negative exponent means you compute the positive power and then take the reciprocal.

Input: x = 2.00000, n = 10
Output: 1024.00000
Explanation: 2 multiplied by itself 10 times equals 1024.

Counter-example to show negative exponents:

Input: x = 2.00000, n = -2
Output: 0.25000
Explanation: 2^(−2) = 1 / 2^2 = 1 / 4 = 0.25.

Intuition

The naive approach multiplies x by itself n times, but n can be as large as 2^31 − 1 — about 2 billion operations, which will always time out. The key insight is that x^n = (x^(n/2))^2: you can square a half-power instead of doing twice the work. Each recursive call halves the exponent, so the total number of multiplications drops from O(n) to O(log n).

Approach 1 — Brute Force (Linear)

Convert a negative exponent to its positive form and multiply x by itself that many times. Simple and correct, but infeasible for the given constraints since n can reach 2 billion.

If n is negative, replace x with 1/x and n with -n.
Initialize result = 1.0.
Multiply result by x exactly n times.
Return result.

1def myPow(x: float, n: int) -> float:
2    if n < 0:
3        x = 1.0 / x
4        n = -n
5    result = 1.0
6    for _ in range(n):
7        result *= x
8    return result

Time: O(n) — one multiplication per unit of exponent.
Space: O(1) — a single accumulator variable.

Approach 2 — Fast Power (Exponentiation by Squaring)

Recurse on half the exponent and square the result. If the exponent is odd, multiply in one extra factor of the base. This gives the same answer with O(log n) multiplications.

Handle the negative case: convert n to its absolute value and record the sign.
Base case: any number to the 0th power is 1.0.
Recurse on exponent // 2 to get the half-result.
If exponent is even, return halfResult * halfResult.
If exponent is odd, return halfResult * halfResult * base — the extra factor covers the leftover.
After recursion, if the original n was negative return 1.0 / result.

1def myPow(x: float, n: int) -> float:
2    def fast_pow(base: float, exponent: int) -> float:
3        if exponent == 0:
4            return 1.0
5        half_result = fast_pow(base, exponent // 2)
6        if exponent % 2 == 0:
7            return half_result * half_result          # even: squaring the half covers it
8        return half_result * half_result * base       # odd: one extra factor of base remains
9    
10    if n < 0:
11        x = 1.0 / x
12        n = -n
13    return fast_pow(x, n)

Time: O(log n) — the exponent halves with every recursive call.
Space: O(log n) — the call stack depth matches the number of halvings.

Complexity Summary

Approach	Time	Space	When to use
Brute Force	O(n)	O(1)	Only for tiny n (n ≤ ~10^6); fails the given constraints
Fast Power	O(log n)	O(log n)	Any time n can be large — the standard interview solution

Common Mistakes

Integer overflow when negating INT_MIN — in Java and C++, -Integer.MIN_VALUE wraps back to Integer.MIN_VALUE because 2^31 doesn't fit in a 32-bit signed int. Always cast n to long before negating or calling abs.
Applying the brute-force loop without noticing the constraint — n can be up to 2^31 − 1 ≈ 2.1 billion. A loop that runs that many multiplications will time out even in C++.
Floor division with a negative exponent in the recursive helper — in Python, -5 // 2 == -3 (floors toward negative infinity), not -2. If you forget to convert n to a positive value before recursing, the exponent never reaches 0 and the recursion runs forever.
Using x from the outer scope inside the helper instead of base — when n was negative you may have already set x = 1.0 / x. If the recursive helper then refers to the outer x variable for the odd-case multiply, it uses the inverted base, silently doubling the inversion.
Choosing exponent == 1 as the base case instead of exponent == 0 — this works for odd exponents but introduces an extra conditional branch and can subtly break the even/odd split logic for edge cases like n = 0.

Pow(x, n) — Solution