The coding question
Implement pow(x, n) without using a built-in power function. n can be negative or zero.
Ask a few questions first
| Ask | What we'll assume |
|---|---|
| What types are x and n? | x is a float, n is an integer that fits in 32 bits. |
| What should a negative n do? | Return 1 divided by x to the power of -n. |
| What about x = 0 with a negative n? | That's dividing by zero. We'll assume it won't be passed in. |
| Do answers need to be exact? | No, normal floating point rounding is fine. |
A couple of examples
| Input | Output |
|---|---|
| x = 2.0, n = 10 | 1024.0 |
| x = 2.1, n = 3 | 9.261000000000001 (floating point for about 9.261) |
| x = 2.0, n = -2 | 0.25 |
Start with brute force
Start at 1 and multiply by x, n times. For negative n, do the same with 1 / x.
Cost: O(n) time. With n up to about 2 billion, that's billions of multiplications, which is too slow.
A better way
x to the 10th is the same as (x squared) to the 5th. So you can square the base and halve the exponent, over and over. If the exponent is odd, peel off one x first and multiply it into the answer.
That's the same as walking through the bits of n: each step squares x, and when the current bit is 1, you multiply that power of x into the answer. The exponent halves every step, so you only need about 31 steps for any 32-bit n.
- If n is negative, flip x to 1 / x and make n positive.
- Start the answer at 1.
- While n is above 0: if n is odd, multiply the answer by x. Then square x and halve n, rounding down.
- Return the answer.
The code
def my_pow(x, n):
if n < 0:
x = 1 / x
n = -n
result = 1.0
while n > 0:
if n % 2 == 1:
result *= x
x *= x
n //= 2
return result| Cost | Why | |
|---|---|---|
| Time | O(log n) | n halves every step |
| Space | O(1) | Just a few numbers, and no recursion |
Test it
Walk through one of the examples out loud, then check the cases that tend to break things:
- n = 0: the loop never runs, so you get 1.0. That's right even for x = 0 by the usual convention.
- x = 0 with a positive n: you get 0.0.
- Negative x: (-2.0, 3) gives -8.0, so the sign comes out right on its own.
- The most negative 32-bit n, -2147483648: Python handles -n fine, and (2.0, -2147483648) gives 0.0 because the true answer is too tiny to store.
Common mistakes
- In Java or C++, writing n = -n when n is the most negative int overflows. Copy n into a 64-bit variable first.
- Forgetting the negative case entirely, or applying 1 / x at the end to the wrong value.
- Writing the recursive version as pow(x, n/2) * pow(x, n/2), which calls itself twice and is back to O(n). Save the half result in a variable.
Follow-up questions
Can you write it recursively?
Yes: work out half = my_pow(x, n // 2) once, then return half * half, times one more x if n is odd. It's O(log n) time but uses O(log n) stack.
What if you need x to the n modulo some number?
Same loop, but take the remainder after every multiply so the numbers stay small. This is called fast modular exponentiation.
Could you raise a matrix to a power the same way?
Yes. Squaring and multiplying work for matrices too, which is how you get the nth Fibonacci number in O(log n) steps.
How the time adds up
| Minutes | What you're doing |
|---|---|
| 0–2 | Clarify. Keep it quick: Meta usually wants two problems in about 45 minutes, so you get about 20 for each |
| 2–4 | Brute force and why it's too slow |
| 4–8 | Explain halving the exponent |
| 8–15 | Write the code |
| 15–18 | Test with the examples and the negative case |
| 18–20 | Follow-up questions |
Key concepts used here
We wrote this sample solution ourselves. Practice Loop is independent and isn't affiliated with or endorsed by Meta.