Pow(x, n) — InterviewPrepKit

Solving tips

An O(n) loop is hopeless with |n| up to ~2e9; use binary exponentiation (exponentiation by squaring) for O(log n).
Core recurrence: x^n = (x^(n/2))^2 for even n, times an extra x for odd n; compute the half once and reuse it (don't recompute).
Handle negative n by using 1/x with a positive exponent; note -(-2^31) overflows in fixed-width languages (Python is safe).
Iterative form reads n's bits: square x each step, multiply into result when the low bit is set. Remember n == 0 returns 1.0; O(log n) time, O(1) space.

Problem

Implement pow(x, n), which raises the floating-point number x to the integer power n (that is, compute x**n). The exponent n can be negative, zero, or positive.

You should not lean on a library power function — the task is to compute it efficiently yourself, in far fewer than n multiplications.

Examples

x = 2.0, n = 10 → 1024.0 — 2 multiplied by itself ten times.
x = 2.1, n = 3 → 9.261000000000001 — ordinary floating-point cube (tiny rounding is expected).
x = 2.0, n = -2 → 0.25 — a negative exponent means 1 / x**|n|, so 1 / 4.

Constraints

-100.0 < x < 100.0
-2^31 <= n <= 2^31 - 1 (n fits in a 32-bit signed integer).
x is nonzero when n is negative; the result stays within double-precision range.
Because |n| can be ~2 billion, an O(n) loop is far too slow — you need O(log n).

Think about it first

Hint 1

Multiplying `x` by itself `n` times is O(n) — with `n` up to two billion, that's hopeless. Can you reuse partial results so each step roughly *doubles* the exponent you've already covered?

Hint 2

`x**n = (x**(n/2))**2` when `n` is even, and `x * (x**((n-1)/2))**2` when `n` is odd. Computing `x**(n/2)` once and squaring it halves the problem each time — that's O(log n) multiplications.

Hint 3

Handle a negative exponent by computing the positive power and taking the reciprocal. Watch the value `n = -2^31`: negating it overflows in fixed-width languages, though Python's big ints are safe — still, convert to a positive exponent carefully.

TL;DR

Binary (fast) exponentiation — square the base while halving the exponent — O(log n) time, O(1) space iterative (or O(log n) stack recursive).

Approach 1 — Brute force (multiply n times)

Multiply x into an accumulator |n| times, then reciprocate if n was negative.

class Solution:
    def myPow(self, x: float, n: int) -> float:
        if n < 0:
            x, n = 1 / x, -n
        result = 1.0
        for _ in range(n):
            result *= x
        return result

Complexity: O(n) time, O(1) space.

Correct, but with n as large as 2^31 - 1 this is about two billion multiplications — it times out. The constraints are chosen precisely to forbid the linear loop.

Approach 2 — Binary exponentiation, recursive

The insight: exponentiation splits in half. x**n = (x**(n//2))**2 for even n, and one extra factor of x for odd n. Each recursive call halves the exponent, so the depth — and the number of multiplications — is O(log n).

This is fast exponentiation (a.k.a. exponentiation by squaring): a classic divide-and-conquer that turns n multiplications into log n squarings.

class Solution:
    def myPow(self, x: float, n: int) -> float:
        def power(base: float, exp: int) -> float:
            if exp == 0:
                return 1.0
            half = power(base, exp // 2)
            if exp % 2 == 0:
                return half * half
            return half * half * base

        if n < 0:
            return power(1 / x, -n)
        return power(x, n)

Walkthrough with x = 2.0, n = 10:

power(2, 10) → needs power(2, 5), then squares it.
power(2, 5) → needs power(2, 2), squares, times 2 (odd).
power(2, 2) → needs power(2, 1), squares.
power(2, 1) → needs power(2, 0) = 1, squares = 1, times 2 (odd) = 2.
Back up: power(2, 2) = 2*2 = 4; power(2, 5) = 4*4*2 = 32; power(2, 10) = 32*32 = 1024.

Only 4 levels of recursion instead of 10 multiplications — and the gap explodes as n grows.

Complexity: O(log n) time, O(log n) space for the call stack.

Approach 3 — Binary exponentiation, iterative

The insight: the same idea without recursion. Read the exponent bit by bit: keep squaring x (covering x**1, x**2, x**4, x**8, …), and whenever the current low bit of n is 1, fold that power into the result. This is just x**n = product of x**(2^k) over the set bits k of n.

class Solution:
    def myPow(self, x: float, n: int) -> float:
        if n < 0:
            x, n = 1 / x, -n
        result = 1.0
        while n > 0:
            if n & 1:            # current low bit set
                result *= x
            x *= x               # square the base for the next bit
            n >>= 1
        return result

Walkthrough with x = 2.0, n = 10 (1010 in binary):

n (binary)	low bit	result before	x (current power)	result after
1010	0	1	2	1
101	1	1	4	4
10	0	4	16	4
1	1	4	256	1024

The set bits of 10 are at positions 1 and 3, so the answer is 2**2 * 2**8 = 4 * 256 = 1024.

Complexity: O(log n) time, O(1) space — the preferred production form.

Common pitfalls

Forgetting n == 0 → must return 1.0 (any base, including 0.0**0 by convention here).
Negative exponent handling: convert to 1/x with a positive exponent. In fixed-width languages, -(-2^31) overflows; promote to a wider type first. Python’s arbitrary-precision ints sidestep this, but it’s the classic interview gotcha.
Recomputing power(base, exp // 2) twice instead of storing it once — that silently turns O(log n) back into O(n).
Expecting exact floats: 2.1**3 is 9.261000000000001; small rounding is normal, not a bug.

Pattern takeaway

Whenever an operation is associative and you must apply it n times — powers, matrix powers, modular exponentiation — halve the exponent and square the operand: O(n) collapses to O(log n). Reading the exponent’s binary digits (“apply the accumulated square exactly on set bits”) is the reusable iterative skeleton.