The problem
Compute x raised to the power n (n may be negative) faster than multiplying x by itself n times.
Input: x = 2, n = 10 Output: 1024
Picture it
Picture folding paper: each fold doubles the thickness. x¹⁰ = (x⁵)², and x⁵ = x · (x²)². So we look at n in binary: square x at each step, and multiply it into the answer whenever the current bit of n is 1. A negative power means 1 ÷ (positive power).
How to recognise it
- You compute a power of a number where the exponent can be huge (up to about 2 billion).
- Multiplying n times is too slow, but the result is a plain product of identical factors.
- The exponent can be split in halves: x^n is related to (x^(n/2))².
- Looking at the binary digits of n gives a short list of squarings.
- Negative exponents appear, and mean "one divided by the positive power".
Start with brute force
Multiply x by itself n times.
def pow_brute(x, n):
result = 1.0
for _ in range(abs(n)):
result *= x
return result if n >= 0 else 1 / result
Time is O(|n|) and space O(1). With |n| up to 2^31 (about 2.1 billion) that is billions of multiplications, which would take minutes in Python and is too slow for a typical time limit.
From brute force to the idea
- Square instead of repeat. x^10 = (x^5)² and x^5 = x · (x²)². One squaring replaces many multiplications.
- Read n in binary. For example 10 is
1010. Then x^10 = x^8 · x^2, which is the product of the powers x^(2^k) at the positions where the bit is 1. - Walk through the bits. The loop keeps
xequal to x, x², x⁴, x⁸ and so on (x *= x). At each step, if the lowest bit ofnis 1 (n & 1), multiply the result by the currentx. Then drop that bit withn >>= 1. - Handle negative n first.
x, n = 1 / x, -nturns x^(−n) into (1/x)^n, so the loop only sees non-negative exponents. - n = 0 skips the loop and returns 1.
This is the key idea: n has only about 31 binary digits, so about 31 squarings plus up to 31 multiplications give the answer.
The key idea
Fast exponentiation by squaring: O(log n) multiplications.
Python solution
def my_pow(x, n):
if n < 0:
x, n = 1 / x, -n
result = 1
while n:
if n & 1:
result *= x # this power of two is in n
x *= x # square: x, x², x⁴, x⁸ …
n >>= 1
return resultIn the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.
Complexity
| Approach | Time | Space | ||
|---|---|---|---|---|
| Brute force | O(\ | n\ | ): one multiplication per unit of the exponent | O(1) |
| Squaring by bits (shown code) | O(log \ | n\ | ): one loop step per bit, at most 62 multiplications for 32 bits | O(1) |
For n = 2^31 − 1 the shown code does 62 multiplications, while the brute force needs more than 2 billion.
Edge cases
- n = 0: returns 1, even for x = 0 (
my_pow(0, 0)is 1). - Negative exponent (
my_pow(2, -2)): returns 0.25. - Negative base (
my_pow(-2, 3)is −8,my_pow(-2, 4)is 16): the sign follows the parity of n. - x = 0 with a negative exponent:
1 / xraisesZeroDivisionError. The problem says that x = 0 only comes with positive n. - Smallest exponent (n = −2^31): Python integers have no limit, so
-nis fine. In languages with 32-bit integers,-noverflows and needs a wider type. - Overflow and underflow:
my_pow(2.0, 2**31 - 1)returnsinf, andmy_pow(2.0, -1075)returns 0.0. These are float limits, not bugs. - Result type:
my_pow(2, 10)returns the int 1024, while a negative exponent returns a float. - Rounding:
my_pow(2.1, 3)is 9.261000000000001, a small floating-point error that LeetCode accepts.
Common mistakes
- Not handling negative n. The loop never ends, because
-2 >> 1stays at −1 forever. - Forgetting to square
xeach step, so only the first power is used:my_pow(2, 10)becomes 4. - Squaring before the bit test, which uses x² where x is needed:
my_pow(2, 3)becomes 64 (see the quiz).
Compute x^n modulo m (n ≥ 0, all integers), for numbers whose true power is far too large to hold. For x = 2, n = 10, m = 1000 the answer is 24. Describe your approach, then write it if you like.
Compare with our answer
Same loop, but reduce every product modulo m so the numbers stay small. This is valid because (a · b) mod m = ((a mod m) · (b mod m)) mod m.
def pow_mod(x, n, m):
result = 1 % m # 1 % 1 is 0, so m = 1 works
x %= m
while n:
if n & 1:
result = result * x % m
x = x * x % m
n >>= 1
return result
pow_mod(2, 10, 1000) is 24, pow_mod(3, 200, 13) is 9, pow_mod(5, 0, 1) is 0, and it agrees with Python's built-in pow(x, n, m) on thousands of random cases. Time O(log n), space O(1).
A strong answer mentions: reducing after every multiplication, starting from 1 % m, and why modulo does not break the squaring idea.
1. You must find the last digit of 7 raised to the power 10^9. Which approach fits best?
Only about 30 squarings are needed, and the remainders keep the numbers tiny. Floating point cannot represent such a power, and 10^9 multiplications are too many.
2. Why is the shown code O(log n) instead of O(n)?
Shifting n right by one each iteration halves the exponent, so the loop runs once per bit. It never stops early and builds no table.
3. A learner swaps the lines inside the loop, so x *= x comes before the if n & 1: test. What does my_pow(2, 3) return?
The first pass squares x to 4 before the bit is used, then the second bit multiplies by 16: 4 · 16 = 64. Running the variant gives 64 where the right answer is 8.
Score 60% or more and the lesson is marked complete.