Pow(x, n)
Problem statement
You're given a real number x and an integer n. Return x raised to the
power n — that is, x multiplied by itself n times, or, if n is
negative, 1 divided by x raised to the positive version of n.
The catch is n: it can be as large as about 2.1 billion in either
direction, so the obvious "multiply in a loop" answer is too slow, and
negating the smallest possible n can overflow a normal 32-bit integer if
you're not careful.
Examples
Example 1
Input: x = 2.00000, n = 10
Output: 1024.00000
Explanation: 2 multiplied by itself 10 times is 1024.
Example 2
Input: x = 2.10000, n = 3
Output: 9.26100
Explanation: 2.1 × 2.1 × 2.1 = 9.261.
Example 3
Input: x = 2.00000, n = -2
Output: 0.25000
Explanation: A negative exponent means "1 over" — 2⁻² is 1 / 2² = 1/4 =
Hints
x by itself n times works, but what happens to that loop
when n is close to 2 billion?Approach
Optimal: Iterative binary exponentiation
Intuition
This does the exact same halving as the recursive version, but built from
the bottom up instead of the top down, using the binary digits of n
directly. Each bit of n (from least to most significant) says whether the
current power of x (which keeps squaring itself) belongs in the answer.
It's the same trick every fast modular-exponentiation routine uses — walk the exponent's bits, square the base each step, and fold it into the result wherever a bit is set.
Steps
- Widen
nto a 64-bit value; if it's negative, flipxto1/xand make the exponent positive, exactly as in the recursive version. - Start
resultat1.0. - While the exponent is greater than
0:- If its lowest bit is
1, multiplyresultby the currentx. - Square
x(this is what makes each step "worth" the next power of 2). - Shift the exponent right by one bit.
- If its lowest bit is
- Return
result.
Dry run
x = 2.0, n = 10 (binary 1010)
| N (binary) | low bit | result | x after squaring |
|---|---|---|---|
| 1010 | 0 | 1 | 4 |
| 0101 | 1 | 1 × 4 = 4 | 16 |
| 0010 | 0 | 4 | 256 |
| 0001 | 1 | 4 × 256 = 1024 | 65536 |
| 0000 | — loop ends | 1024 | — |
Edge cases: same as the recursive version — the 64-bit widening keeps
n = INT_MIN from overflowing when it's negated.
Complexity
Time O(log n) - same cost as the recursive version: the exponent is halved (via a bit shift) once per iteration.
Space O(1) - no recursion stack, just the running result and a squared copy of `x`.
class Solution:
def myPow(self, x: float, n: int) -> float:
N = n
if N < 0:
x = 1 / x
N = -N
result = 1.0
while N > 0:
if N & 1:
result *= x
x *= x
N >>= 1
return result
if __name__ == "__main__":
print(f"{Solution().myPow(2.00000, 10):.5f}")
print(f"{Solution().myPow(2.10000, 3):.5f}")
print(f"{Solution().myPow(2.00000, -2):.5f}")RecapThe whole problem in a few lines, for the night before
- Spot it: raise a number to a possibly huge (up to ~2³¹) integer
- exponent, positive or negative
- Idea: square-and-halve the exponent instead of multiplying one factor
- at a time —
xⁿ = (x^(n/2))², with one extraxfolded in whennis odd - Cost: O(log n) time either way; O(log n) space recursively, O(1)
- iteratively, versus O(n) time for the naive loop
- Trap: negating the smallest possible 32-bit
noverflows unless you - widen it to a 64-bit type first
Interview follow-ups
What if
ncould be a much larger number that doesn't fit in 64 bits — say, represented as a string of digits?The bit-by-bit halving trick still works, but you can't halve a huge decimal number the same way you halve a machine integer. Convert the exponent to binary digit-by-digit (repeated division by 2 on the big number, or parse it directly if it's given in binary), and drive the same square-and-multiply loop off those bits instead of a native integer's bits. The complexity becomes O(log n) squarings, each one costing whatever big-number multiplication costs.
How would you extend this to compute
x^n mod mfor a huge exponent, as used in cryptography?Take a modulus after every multiplication instead of letting the numbers grow —
result = (result * x) % mandx = (x * x) % mat each step. This keeps every intermediate value bounded byminstead of exploding in size, which is exactly what makes RSA-style modular exponentiation practical for exponents with hundreds of digits.What if you needed to answer many
powqueries with the samexbut differentnvalues?Precompute
x,x²,x⁴,x⁸, … up to the largest power of two you'll need, once. Each query then just multiplies together the precomputed powers whose bit positions match the query'sn, turning each individual query into O(log n) multiplications with no repeated squaring work across queries.
Frequently asked questions
The connection isn't searching — it's the halving. Binary search shrinks the range it's looking at by half each step; fast exponentiation shrinks the exponent by half each step. Both are divide-and-conquer recursions that turn a linear amount of work into a logarithmic amount by cutting the problem in half every time, which is why sheets that group by pattern often place them together.
A 32-bit signed integer's range is asymmetric: it can hold -2147483648 but
its positive counterpart, 2147483648, is one more than the largest value
the same type can hold (2147483647). Writing -n directly on the smallest
possible n overflows. Copying n into a 64-bit long before negating
sidesteps the whole issue, since the 64-bit range comfortably holds both.
The same halving trick — square-and-multiply — is the basis of the
modpow/fast modular exponentiation used in RSA and Diffie-Hellman key
exchange, so an interviewer using this problem is often checking whether you
can recognize and implement that pattern, not just whether you can compute a
power.
Both accumulate floating-point rounding error, but the fast approach does
roughly log₂(n) multiplications instead of n, so it accumulates far less
rounding error along the way — one more reason it's the better choice
even ignoring speed.
Two, usually: forgetting the INT_MIN negation overflow, and forgetting
that n = 0 should return 1.0 for any x, including x = 0 (the problem
guarantees x isn't 0 when n could make that division undefined).
