Pow(x, n)

Pow(x, n) is the standard test of fast exponentiation, an idea that appears far beyond this one problem: modular inverses, matrix powers for Fibonacci, and cryptography all use it. The interviewer wants to see the O(log n) idea, a correct handling of negative exponents, and — often — the modular version.

The problem

Implement a function that returns x raised to the power n, where x is a floating-point number and n is an integer.

Example 1. x = 2.0, n = 10 → 1024.0.

Example 2. x = 2.1, n = 3 → 9.261 (floating point prints 9.261000000000001).

Example 3. x = 2.0, n = -2 → 0.25. A negative power is 1 over the positive power: 1 / 2² = 1/4.

Constraints. −100 < x < 100. n is a 32-bit signed integer, so −2³¹ ≤ n ≤ 2³¹ − 1. Either x is non-zero or n is positive.

Clarifying questions

• Can n be negative? Yes. Handle it by inverting x.
• Can x be 0 with a negative n? No — the constraints rule out division by zero.
• Can I use ** or math.pow? No; that is the thing being implemented.
• How exact must the answer be? Within normal floating-point rounding, like the built-in.

Approach 1: the simple way

Multiply x by itself n times.

1def pow_naive(x: float, n: int) -> float:2    """Brute force: n multiplications."""3    if n < 0:4        x, n = 1 / x, -n5    result = 1.06    for _ in range(n):7        result *= x8    return result

O(n) time and O(1) space. With n up to 2³¹ − 1, about 2.1 × 10⁹, that is far too slow. Measured in Python, ten million multiplications took 0.2 seconds, so two billion would take around 40 seconds.

The key insight

Squaring skips ahead. x⁸ = (x⁴)², and x⁴ = (x²)². So x⁸ needs three multiplications — square, square, square — not seven.

What about exponents that are not powers of two? Every positive integer is a sum of distinct powers of two — that is what its binary form says. Take n = 13:

13 = 1101 in binary = 8 + 4 + 1so x^13 = x^8 × x^4 × x^1

The powers x¹, x², x⁴, x⁸ each come from squaring the one before. The 1 bits of n say which of them to multiply into the result. So the work is one squaring per bit of n, plus one multiplication per 1 bit: at most 2 × 31 = 62 for any 32-bit n.

Approach 2: square and multiply, reading bits from the bottom

1def my_pow(x: float, n: int) -> float:2    """Fast exponentiation: O(log n) multiplications."""3    if n < 0:4        x, n = 1 / x, -n            # x^(-n) = (1/x)^n5    result = 1.06    base = x                        # holds x^1, x^2, x^4, x^8, ...7    while n:8        if n & 1:                   # this power of two is part of n9            result *= base10        base *= base                # move to the next power of two11        n >>= 1                     # drop the bit just handled12    return result

Step by step:

1. Turn a negative exponent into a positive one by inverting x.
2. base walks through x¹, x², x⁴, x⁸ …, one squaring per loop.
3. If the lowest bit of n is 1, that power belongs in the answer: multiply it into result.
4. Shift n right to look at the next bit. Stop when no bits are left.

Dry run for n = 13 (binary 1101), writing powers of x:

result picked up x¹ (bit 0), x⁴ (bit 2) and x⁸ (bit 3) — exactly the 1 bits of 1101. The loop did 4 squarings and 3 multiplications into result: 7 in all, against 12 for the naive loop. For n = 10⁹ (30 bits, 13 of them 1) it does 43 multiplications instead of a billion, and took 8 microseconds.

Complexity. O(log n) time: one round per bit of n. O(1) space.

Approach 3: the recursive form

The same idea, top-down: xⁿ = (x^(n/2))² when n is even, and x × (x^(n/2))² when n is odd.

1def my_pow_recursive(x: float, n: int) -> float:2    """x^n = (x^(n//2))^2, times x if n is odd. O(log n) time and depth."""3    if n < 0:4        return my_pow_recursive(1 / x, -n)5    if n == 0:6        return 1.07    half = my_pow_recursive(x, n // 2)    # compute once, use twice8    return half * half * x if n % 2 else half * half

O(log n) time and O(log n) stack depth — at most 32 frames for a 32-bit n, so no risk of hitting Python's recursion limit.

Computing half once is the whole optimisation. Writing my_pow_recursive(x, n // 2) * my_pow_recursive(x, n // 2) makes two calls at every level. The call tree then doubles at each of the log n levels, giving 2^(log n) = n calls — back to O(n).

All three versions agreed with Python's own x ** n on 300 random inputs, with exponents from −60 to 60.

The modular version

When the answer is an integer "modulo m", the same loop works with a remainder after every multiplication:

1def mod_pow(base: int, exponent: int, modulus: int) -> int:2    """base^exponent mod modulus in O(log exponent) steps."""3    result = 14    base %= modulus5    while exponent:6        if exponent & 1:7            result = result * base % modulus8        base = base * base % modulus9        exponent >>= 110    return result

Every value stays below the modulus, so nothing grows. Python's built-in pow(base, exponent, modulus) does exactly this — use it in real code, and be able to write it when asked. It matched the built-in on 300 random cases with exponents up to 10¹².

Edge cases

• n = 0. The loop does not run; the answer is 1.0, even for x = 0.
• Negative n. Inverting x first keeps the loop simple. my_pow(2.0, -2) gives 0.25.
• n = −2³¹. In Java or C++, -n overflows, because 2³¹ does not fit in a 32-bit int. Copy n into a 64-bit long before negating. Python has no such limit; my_pow(2.0, -2**31) returns 0.0 (the true value is too small for a float), and my_pow(1.0, -2**31) returns 1.0.
• Negative x. my_pow(-2.0, 3) is -8.0; the sign comes out right because odd powers keep an odd number of negative factors.

Follow-ups

• "Return the answer modulo 10⁹ + 7." Use mod_pow above: reduce after every multiplication.
• "Compute the n-th Fibonacci number for n = 10¹⁸." Raise the 2 × 2 matrix [[1, 1], [1, 0]] to the n-th power by the same square-and-multiply loop, with matrix multiplication instead of number multiplication: O(log n).
• "Compute a modular inverse." For a prime modulus p, the inverse of b is pow(b, p - 2, p) — fast exponentiation again.