A linear multiplication chain follows the definition of a power. It also ignores the only fact that matters at interview scale: the exponent can be halved.

The core Pow(x, n) solution is exponentiation by squaring:

1. Convert a negative exponent into a reciprocal problem.
2. Process a nonnegative exponent one binary digit at a time.
3. Multiply the answer when the current exponent is odd.
4. Square the base and halve the exponent.

That turns O(|n|) multiplication into O(log |n|) multiplication.

Read the contract and choose the target

We need to return the mathematical value of x^n, where:

• x is a floating-point value.
• n is a signed integer.
• n may be positive, zero, or negative.
• Negative powers mean reciprocals: x^-k = 1 / x^k.
• The exponent may reach the 32-bit signed boundary, including -2^31.

The straightforward implementation is:

result = 1.0

for _ in range(abs(n)):
    result *= x

if n < 0:
    return 1.0 / result

return result

This mirrors the definition of exponentiation, but it performs one multiplication for every unit in |n|. An exponent near two billion makes that approach irrelevant under interview constraints.

The target is therefore clear:

Make the remaining exponent shrink by a constant factor at every step.

That is the recognition signal for divide and conquer.

Spot the halving structure

For a nonnegative exponent n, separate even and odd cases.

If n is even:

[ x^n = (x^2)^{n/2} ]

For example:

[ x^{10} = (x^2)^5 ]

We square the base and halve the exponent.

If n is odd:

[ x^n = x \cdot x^{n-1} ]

Since n - 1 is even:

[ x^n = x \cdot (x^2)^{(n-1)/2} ]

For example:

[ x^5 = x \cdot (x^2)^2 ]

The extra x must be preserved before the exponent is halved.

This is exponentiation by squaring, also called binary exponentiation or fast power. The name describes the mechanism: the base advances through powers

[ x,\ x^2,\ x^4,\ x^8,\ldots ]

and the binary representation of the exponent tells us which of those powers belong in the result.

For n = 13:

[ 13 = 8 + 4 + 1 ]

So:

[ x^{13} = x^8 \cdot x^4 \cdot x ]

The algorithm discovers those set bits from right to left. Each iteration either absorbs the current base into the result or skips it, then advances the base by squaring.

This is divide and conquer, but the speedup does not come from memoizing many overlapping subproblems. There is one shrinking subproblem at each step. The leverage comes from replacing the exponent with roughly half its old value.

Normalize negative exponents before the core algorithm

Negative exponents should not complicate the repeated-squaring helper. Normalize them first.

For n < 0:

[ x^n = \left(\frac{1}{x}\right)^{-n} ]

So we can replace:

x = 1 / x
n = -n

Then the core algorithm only handles n >= 0.

That separation gives the helper one clean contract:

Given a base and a nonnegative exponent, return the base raised to that exponent.

There are two boundaries to handle deliberately.

n = 0

For a nonzero base:

[ x^0 = 1 ]

The iterative algorithm naturally starts with result = 1.0 and performs no loop iterations when the exponent is zero.

The problem contract excludes the invalid zero-base, negative-exponent combination. Do not invent behavior for a case the contract rules out.

n = -2^31

In a fixed-width signed integer type, the range is asymmetric:

• Minimum: -2^31
• Maximum: 2^31 - 1

Negating -2^31 produces 2^31, which cannot fit in a signed 32-bit integer. A solution that simply writes n = -n may overflow before the algorithm begins.

In Python, integers have arbitrary precision, so -n is safe. The boundary still matters because the same reasoning must survive translation to Java, C++, or another fixed-width language. A portable implementation widens the exponent before negating it.

The representation decision is part of the solution, not a minor language detail.

Derive the recursive recurrence and prove it

Define:

fast_power(base, exponent)

for exponent >= 0.

The base case is:

[ \text{fast_power}(base, 0) = 1 ]

For a positive exponent, compute the half-result exactly once:

[ half = \text{fast_power}(base, \lfloor exponent/2 \rfloor) ]

Then:

• If exponent is even, return half * half.
• If exponent is odd, return half * half * base.

The recursive Python version is:

def fast_power(base: float, exponent: int) -> float:
    if exponent == 0:
        return 1.0

    half = fast_power(base, exponent // 2)
    squared = half * half

    if exponent % 2 == 0:
        return squared

    return squared * base

The phrase exactly once matters. This is wrong:

return fast_power(base, exponent // 2) * fast_power(base, exponent // 2)

It computes the same half-problem twice. The recurrence remains mathematically valid, but the implementation throws away the divide-and-conquer savings.

Correctness argument

We can prove the helper by induction on exponent.

• Base case: when exponent == 0, the function returns 1.0, which equals base^0.
• Even case: assume the recursive call correctly returns base^(exponent // 2). Squaring it gives base^exponent.
• Odd case: the squared half gives base^(exponent - 1). Multiplying by base gives base^exponent.
• Negative input: sign normalization changes x^n into (1/x)^(-n), which is mathematically equal to the original value.

The proof follows the code because the code follows the recurrence. That is the standard to aim for in an interview: each branch should correspond to an identity you can state aloud.

Recursive trace: 2^10

The recursive calls shrink the exponent like this:

fast_power(2, 10)
fast_power(2, 5)
fast_power(2, 2)
fast_power(2, 1)
fast_power(2, 0)

The calls then return upward:

2^0 = 1
2^1 = 1^2 * 2 = 2
2^2 = 2^2 = 4
2^5 = 4^2 * 2 = 32
2^10 = 32^2 = 1024

For 2^-3, normalize first:

base = 1 / 2 = 0.5
exponent = 3

Then:

0.5^3 = 0.125

The negative exponent disappears from the recursive algorithm. That is exactly what we want: sign handling at the boundary, exponentiation in the core.

Translate the proof into iterative state

Recursion makes the recurrence obvious. Iteration makes the storage cost constant and exposes every state transition.

Use three variables:

• result: the power already assembled from processed exponent bits.
• base: the current power-of-two contribution, starting at x, then becoming x², x⁴, x⁸, and so on.
• exponent: the part of the nonnegative exponent that has not been processed yet.

The key invariant is:

[ result \cdot base^{exponent} = \text{target} ]

Here, target is the normalized power we need to compute. Initially:

result = 1
base = x
exponent = n

Therefore:

[ 1 \cdot x^n = x^n ]

The loop preserves that equality in both branches.

• If exponent is odd, multiply result by base.
• Square base.
• Halve exponent.

When the exponent is odd, write it as 2q + 1:

[ result \cdot base^{2q+1}

(result \cdot base) \cdot (base^2)^q ]

That is exactly the state update.

When the exponent is even, write it as 2q:

[ result \cdot base^{2q}

result \cdot (base^2)^q ]

Again, the update preserves the invariant.

State trace: 2^13

The following table shows the state before each iteration. The action column explains whether the current binary contribution is absorbed.

Exponent	Result	Base	Action
13	1	2	Odd: multiply result by 2
6	2	4	Even: skip
3	2	16	Odd: multiply result by 16
1	32	256	Odd: multiply result by 256
0	8192	65536	Stop

The final result is:

[ 2^{13} = 8192 ]

The state is not magic. It is a compressed record of the binary expansion:

[ 13 = 1 + 4 + 8 ]

The result absorbs 2, 2^4, and 2^8.

Canonical Python implementation

def my_pow(x: float, n: int) -> float:
    if n < 0:
        x = 1.0 / x
        n = -n

    result = 1.0
    base = x
    exponent = n

    while exponent > 0:
        if exponent % 2 == 1:
            result *= base

        base *= base
        exponent //= 2

    return result

This is the version I would usually submit in Python. The state is explicit, the helper contract is unnecessary, and the algorithm uses constant auxiliary space.

The % 2 check is readable and makes the odd-exponent contribution visible. Bitwise operations are equivalent for nonnegative integers:

if exponent & 1:
    result *= base

exponent >>= 1

They are not required to understand or derive the algorithm. Use them only if they improve clarity in the language and codebase you are working in.

Invariant: after every iteration, result * base**exponent equals the normalized target power. The loop terminates when no exponent remains, so result is the answer.

Complexity and implementation choices

At every iteration, the exponent is replaced by integer division by two. Starting from |n|, that takes:

[ O(\log |n|) ]

iterations.

Each iteration performs a constant amount of work:

• One parity check.
• At most one multiplication into result.
• One squaring of base.
• One halving operation.

Therefore the running time is O(log |n|).

The exact multiplication count depends on the exponent's binary representation:

• One squaring per processed exponent level.
• One additional result multiplication for each set bit.

The asymptotic bound stays logarithmic.

Space differs by implementation:

Form	Time	Auxiliary space	Main tradeoff
Recursive	`O(log	n	)`
Iterative	`O(log	n	)`

Recursion is useful during derivation because the mathematical recurrence maps cleanly to code. Iteration is usually the better interview submission when constant auxiliary space, stack avoidance, and integer-boundary control matter.

Derive recursively if that makes the proof visible. Submit iteratively when the state is clear.

Break the plausible implementations

A solution can look elegant and still fail at the edges. Test the obligations, not just the happy path.

Identity and reciprocal cases

Check:

x = 5.0, n = 0   -> 1.0
x = 5.0, n = 1   -> 5.0
x = 5.0, n = -1  -> 0.2

These expose missing identity handling and incorrect negative normalization.

Even and odd exponents

Check both signs and both parities:

2^10   = 1024
2^-2   = 0.25
2^-3   = 0.125

Odd exponents are especially useful because they expose the common mistake of squaring and halving without preserving the extra current base.

Special bases

Test:

• x = 1.0: every valid exponent returns 1.0.
• x = -1.0: the result depends on whether n is even or odd.
• Fractional bases such as 0.5.
• Negative bases, where parity controls the sign.
• x = 0 with a positive exponent.

Avoid using floating-point equality as the main correctness argument for arbitrary fractional inputs. The algorithm should preserve the mathematical recurrence; floating-point representation can still introduce ordinary rounding.

Minimum signed exponent

Test:

n = -2^31

In Python, arbitrary-precision integers make the negation safe. In a fixed-width language, widening before negation is necessary.

Common failures

Watch for these implementations:

• Repeated multiplication, which is linear in |n|.
• Recursive computation of the same half-result twice.
• Missing the odd-step multiplication.
• Returning 0 or x for n = 0 instead of 1.
• Claiming recursive space is O(1).
• Negating the minimum signed integer in its original narrow type.
• Letting negative-exponent handling leak into every branch of the core algorithm.
• Using a built-in power function when the task requires deriving the algorithm.

Read the error. Trace the state. Fix the assumption. That workflow is more reliable than memorizing a code template.

The transferable pattern

When an integer parameter can be halved while the current contribution can be squared, inspect the problem for binary exponentiation or a related divide-and-conquer recurrence.

For this problem, the implementation checklist is short:

1. Define the helper or loop around a nonnegative exponent.
2. Normalize negative powers before entering the core algorithm.
3. Preserve the odd contribution.
4. State the invariant.
5. Decide how the integer representation handles the minimum signed value.
6. Choose recursion for direct recurrence mapping or iteration for constant space.

The broader recognition rule is simple:

If the work shrinks by halving and the reusable contribution squares, stop multiplying one step at a time. Compress the work into powers of two.