Pow(x, n)
Implement pow(x, n), which computes x raised to the power n — including negative exponents — without the built-in power operator.
- -100.0 < x < 100.0
- -2³¹ <= n <= 2³¹-1
- n is an integer.
- Either x is not zero or n > 0.
- -10⁴ <= xn <= 10⁴
Intuition
Powx n implements pow(x, n) without the built-in operator, including negative exponents. Multiplying x by itself n times is correct but O(n), and with n reaching 2³¹ that is far too many multiplications.
The improvement comes from a simple algebraic identity. Since x^n = (x²)^(n/2), squaring the base lets you halve the exponent — and halving repeatedly reaches zero in about log₂(n) steps rather than n:
- Square the base and halve the exponent; when the exponent is odd, fold one factor of the current base into the result first.
The odd case is what makes it exact. If n is odd, halving loses a factor, so that factor is multiplied into the accumulator before the halving. This is binary exponentiation, and it is equivalent to reading the exponent's binary representation bit by bit.
Negative exponents are just a reciprocal: compute x^|n| and return 1 / result.
There is one genuine trap in fixed-width languages. n = -2³¹ cannot be negated — its absolute value overflows a signed 32-bit integer, and negating it silently yields itself. Converting to a 64-bit type before taking the absolute value avoids it, and this is the edge case the problem is really testing.
Exponentiation by squaring: halve the exponent each round instead of decrementing it, turning O(n) into O(log n). The binary expansion of n is what the loop is really reading — each n % 2 asks whether the current squared value belongs in the product. The same doubling idea powers modular exponentiation and matrix power.
Approach
Before reading on: price up what the brute force costs here, then ask what you would need to remember from the left to avoid re-scanning. Aim for O(log n) time and O(1) space.
See why the naive loop is too slow
Multiplying n times is O(n), and n can reach 2³¹. The exponent's size, not the base, is what makes this infeasible — which points at halving the exponent rather than optimising the multiplication.
Handle the negative exponent first
A negative power is a reciprocal: compute x^|n| and return 1 / result. Taking the absolute value up front keeps the main loop dealing only with non-negative exponents.
Guard the integer overflow
-2³¹ has no positive counterpart in signed 32-bit arithmetic, so negating it returns itself and the loop misbehaves. Convert to a 64-bit type before taking the absolute value — this is the edge case the problem exists to test.
Fold in a factor when the exponent is odd
If the current exponent is odd, multiply the accumulator by the current base before halving. Halving an odd number loses a factor, and this step is what puts it back.
Square the base and halve the exponent
Each iteration replaces the base with its square and the exponent with half of it, using integer division. The loop ends when the exponent reaches zero, after about log₂(n) iterations.
Cost of binary exponentiation
The exponent halves each step, giving O(log n) time and O(1) space for the iterative version. The recursive form has the same time bound but adds O(log n) stack frames.
Solution & live demo
Common pitfalls
Multiplying in a loop n times
for _ in range(n):
result *= xwhile n > 0:
if n % 2 == 1: result *= x
x *= x
n //= 2With n up to 2^31 that's billions of iterations. Squaring the base while halving the exponent reaches the same answer in about 31 steps.
Negating the exponent without inverting the base
if n < 0:
n = -nif n < 0:
x, n = 1 / x, -nA negative exponent means the reciprocal, so flipping only the sign computes x^|n| and returns a number that is wrong by a factor of x^(2n). Both must change together.
Squaring only when the bit is set
if n % 2 == 1:
result *= x
x *= x
n //= 2if n % 2 == 1: result *= x x *= x n //= 2
x tracks base^(2^k) and must double on every iteration to stay aligned with the bit position. Squaring conditionally desynchronises it from n, so later bits multiply in the wrong power.
Edge cases
Any base to the zero power is 1; the loop never runs and result stays 1.
Compute the positive power, then take the reciprocal 1 / result.
Still O(log n); squaring stays at 1 or alternates sign correctly.