Pow(x, n)
WHAT IT SAYS
Compute x raised to the power n, where n can be negative and very large.
WHAT IT'S REALLY ASKING
"x^n costs n multiplications only if you insist on climbing one step at a time. But x^10 is (x^5) squared — so once you hold x^5, the next doubling is ONE multiply, not five. How many doublings does it take to reach n, and why is that the whole algorithm?"
Multiply n times
O(n) time, O(1) spaceStart at 1 and multiply by x, n times over. If n is negative, do it |n| times and take the reciprocal.
WHERE THE WORK IS WASTED — Watch it compute x^10. It builds x^5 on the way, one multiply at a time — and then keeps grinding out five more multiplies to reach x^10, when a single squaring of the x^5 it was ALREADY HOLDING would have finished the job. The loop throws away exactly the intermediate result that would have halved its remaining work, and it does this at every level. Multiplication is the operation that combines two halves; the naive loop refuses to use it that way.
One multiply halves the exponent. n halves log n times.
Two readings of the same fact, and both are worth having. The recursive reading: x^n is (x^(n/2))^2 when n is even, and x times (x^((n-1)/2))^2 when n is odd. Either way, one multiplication (or two) buys you a HALVING of the exponent. And an integer can only be halved log2(n) times before it reaches zero — that is not an estimate, it is the entire complexity proof, and it is the reason 2^62 takes about 62 multiplies instead of four quintillion. The binary reading, which is the one to keep: write n in base 2. Then x^n is the product of x^(2^i) over exactly the set bits of n, because the exponents ADD when you multiply. So repeatedly squaring the base manufactures a series of coins — x^1, x^2, x^4, x^8, x^16 — and n's binary representation is the shopping list telling you which coins to spend. Each coin is produced by one squaring from the previous one, so nothing is ever computed twice, and each is spent at most once. That framing is why this is not really a fact about numbers. It works for anything associative — matrix products (Fibonacci in log n), modular products, min-plus products on graphs — because the only property used was that combining is associative, so the halves may be grouped freely. Two edges that are the real interview: negative n means invert at the end, and n equal to the most negative 32-bit integer cannot be negated in 32 bits at all — copy it into a 64-bit value before you flip its sign.
Square the base, spend the set bits
O(log n) time, O(1) spaceSet result to 1. While n is non-zero: if the low bit of n is 1, multiply result by the current base; then square the base and shift n right by one. If n was negative, take the reciprocal of the result at the end, having widened n to 64 bits before negating it.
Halve the Exponent
YOU'LL SEE IT AGAIN WHEN
- You are applying an associative operation n times, and n is large enough that an O(n) loop is out of the question.
- The obvious loop recomputes the same half twice — it holds the answer to the sub-problem and then discards it.
- n's binary expansion can be read as instructions: which precomputed doublings to combine.