Repository navigation
171 — Pow x n
LeetCode 50 · Medium. Implement pow(x, n), which calculates x raised to the power n (xⁿ), where x is a Double and n is an Int that may be negative (meaning xⁿ = 1 / x^(-n)).
The obvious way to compute x to the tenth power is to multiply x by itself ten times. But notice: x¹⁰ = (x⁵)², and x⁵ = x * (x²)². Each of those inner expressions only needs to be computed once and then squared — you don't need to separately multiply x by itself ten separate times if you're willing to square intermediate results instead. Squaring a value you already have doubles the exponent for the price of one multiplication, so instead of walking down from n to 0 one step at a time, you can cut n in half at every step.
x^10 10 in binary: 1010
x^10 = (x^5)^2 step: exponent 10 -> 5 (even: just square the base)
x^5 = x * (x^2)^2 step: exponent 5 -> 2 (odd: peel off one factor of x first)
x^2 = (x^1)^2 step: exponent 2 -> 1 (even: just square the base)
x^1 = x * (x^0)^2 step: exponent 1 -> 0 (odd: peel off one factor of x first)
x^0 = 1 base case
only 4 multiplications of the running base, instead of 10
"Compute x to the power n efficiently" — especially when n can be large — is the fast-exponentiation (binary exponentiation) signal: repeatedly halve the exponent, squaring the base each time, and fold in one extra factor of the base whenever the current exponent is odd. Watch for the two edge cases the problem statement is testing for: n == 0 (x⁰ = 1 for any x, including 0), and negative n (xⁿ = 1 / x^(-n)).
Multiply x by itself |n| times, then invert the result if n was negative.
func myPowBruteForce(_ x: Double, _ n: Int) -> Double {
if n == 0 { return 1.0 }
// Swift's Int is 64-bit, so negating even the smallest Int32 (n's practical range
// on LeetCode) never overflows here.
let exponent = n < 0 ? -n : n
var result = 1.0
for _ in 0..<exponent {
result *= x
}
return n < 0 ? 1.0 / result : result
}
// smoke test
print(myPowBruteForce(2.0, 10)) // 1024.0
print(myPowBruteForce(2.0, -2)) // 0.25
print(myPowBruteForce(2.1, 3)) // 9.261000000000001
print(myPowBruteForce(1.0, 1000)) // 1.0 -- fine here, but this loop genuinely runs
// 1000 times; at n = 2,147,483,647 (LeetCode's
// actual upper bound) this same loop would run
// over two billion times, which is exactly the
// scaling problem the optimal solution below fixesBig-O: O(n) time — one multiplication per unit of exponent. O(1) space.
Halve the exponent every iteration instead of decrementing it by one. Square the base each step (doubling what it represents), and fold in one extra factor of the current base into the result whenever the exponent is odd, since an odd exponent can't be evenly split in half.
func myPow(_ x: Double, _ n: Int) -> Double {
var base = x
var exponent = n < 0 ? -n : n
var result = 1.0
while exponent > 0 {
if exponent % 2 == 1 {
result *= base
}
base *= base
exponent /= 2
}
return n < 0 ? 1.0 / result : result
}
// smoke test — same cases as the brute force
print(myPow(2.0, 10)) // 1024.0
print(myPow(2.0, -2)) // 0.25
print(myPow(2.1, 3)) // 9.261000000000001
print(myPow(1.0, 2147483647)) // 1.0Big-O: O(log n) time — the exponent is halved every iteration. O(1) space.
The brute force treats every unit of the exponent as independent work, multiplying n separate times. But x^n doesn't need to be built up one factor at a time — it can be built up by doubling, since x^(2k) = (x^k)². Halving the exponent each step means the loop only runs log₂(n) times instead of n times, with the odd-exponent case (x^(2k+1) = x * (x^k)²) making sure no exponent value is unreachable by pure halving. This is the same divide-and-conquer shape as binary search's T(n) = T(n/2) + O(1) recursion — except here the "search space" being halved each step is the exponent itself, not a sorted range being probed for a target. It's worth being honest that Pow(x, n) isn't searching for anything; the connection to Binary Search is about the shape of the halving recursion, not the problem's goal.
-
Arrays and Strings — disclosed as a stretch, not a natural fit: there's no array or string anywhere in this problem's input or output. The only thread connecting it to this chapter is that the optimal loop implicitly walks the bits of
n's binary representation one at a time (each iteration inspects one bit viaexponent % 2), the same "linear scan over a sequence of elements" shape this chapter covers for genuine arrays — but that's a structural echo, not a real array or string being processed. -
Binary Search — a defensible link: both repeatedly halve a search space doing
O(1)work per halving, the same recursion shape, even though Pow(x, n) is halving an exponent rather than searching sorted data for a target.
Pow(x, n) is squaring your way there instead of walking — halve the exponent every step, square the base to match, and grab one extra factor whenever the exponent's odd.
- Why does squaring the base and halving the exponent simultaneously preserve the mathematical value of
base^exponentat every step of the loop? - Walk through why the
if exponent % 2 == 1 { result *= base }line is necessary — what would go wrong for an odd exponent like5if it were removed? - Both solutions compute
let exponent = n < 0 ? -n : nup front and invert the final result at the end, rather than trying to handle negativeninside the main loop. Why is handling the sign once, outside the loop, simpler than threading it through every iteration? - The chapter argues the Binary Search connection is about recursion shape, not problem goal. In your own words, what's the concrete difference between "halving a search space to find a target" and "halving a search space to compute a running product"?