Pow(x, n)

Problem

Cryptographic protocols and physics simulations raise numbers to large powers millions of times per second. Naive repeated multiplication is O(n) and too slow for large exponents. Given a float x and integer n (which may be negative or zero), return x^n using the divide-and-conquer approach that runs in O(log n) time.

Example 1:

Input: x = 5.0, n = 3
Output: 125.0

Example 2:

Input: x = 2.0, n = -5
Output: 0.03125
Explanation: 2^-5 is the reciprocal of 2^5 = 32.

Example 3:

Input: x = 7.0, n = 0
Output: 1.0
Explanation: any number raised to the zeroth power is 1.

Example 4:

Input: x = 4.0, n = 3
Output: 64.0

Constraints:

• -100.0 < x < 100.0
• -10^4 <= n <= 10^4
• n is an integer.
• Either x != 0 or n > 0.
• -10^4 <= x^n <= 10^4

Solution Breakdown

Approach: Divide-and-conquer (fast / binary exponentiation) by halving the exponent.

The algorithm rests on one identity: x^n = (x^(n//2))^2, with one extra * x when n is odd (because integer division drops the remainder, so n//2 + n//2 = n - 1). Instead of multiplying x by itself n times, the function recurses once on the half-exponent, stores that result in half, and squares it - turning O(n) multiplications into O(log n) because the exponent is cut in half at every level. Storing half once and reusing it is what makes this fast: calling my_pow(x, n//2) twice would re-branch and lose the savings. The base case n == 0 returns 1.0, since any number to the zero power is 1. Negative exponents are peeled off first: x^(-n) = 1 / x^n, so the top guard recurses on -n and inverts the result, after which the rest of the function only ever sees non-negative exponents.

Trace my_pow(4.0, 3): n=3 odd, recurse to n=1; n=1 odd, recurse to n=0 returning 1.0, then 1*1*4 = 4.0; back at n=3, 4*4*4 = 64.0. Two recursive calls, not two naive multiplications plus the whole chain.

Edge cases: n == 0 returns 1.0 (checked before any recursion). Negative n is handled by the n < 0 guard inverting a positive-exponent result, so my_pow(2.0, -5) = 0.03125. A fractional or 1.0 base works unchanged since the recurrence is purely multiplicative.

Complexity: O(log n) time, O(log n) space - the exponent halves each call, so the recursion is log2(n) levels deep with one frame per level.