Problem Statement
Pow(x, n)
We need to compute x raised to the power n, written as x^n. That just means x multiplied by itself n times. For example, 2^10 means multiply 2 by itself 10 times, which gives 1024. The obvious way is to start at 1 and multiply by x exactly n times. That works, but if n is huge (like a billion), that is a billion multiplications. The trick we use is called exponentiation by squaring, also known as fast power. The idea: instead of taking one step at a time, we cut the work in half at every step. Here is the key fact. If n is even, then x^n is the same as (x squared) raised to half the power: x^n = (x^(n/2))^2. If n is odd, we peel off one x and then do the same: x^n = x times (x^(n/2))^2. Because we keep halving n, we finish in about log n steps instead of n steps. For negative powers, x^(-n) just means 1 divided by x^n, so we flip x to 1/x and make n positive.
Signals to notice
Brute force first
Multiply x by itself n times — O(n). Linear in the exponent.
The key insight
Binary exponentiation: x^n = (x²)^(n/2) if even, x × x^(n-1) if odd. Halves n each step. O(log n).
Trace it on x=2.0, n=10
init: n>=0, so result=1, x=2, n=10 n=10 even -> no mult; square x=4, halve n=5 n=5 odd -> result=1*4=4; square x=16, halve n=2 n=2 even -> no mult; square x=256, halve n=1 n=1 odd -> result=4*256=1024; square x=65536, halve n=0 n=0 -> loop ends, return result=1024.0
What must stay true
Squaring the base and halving the exponent reduces any exponent to 0 in O(log n) steps. Negative n: compute x^|n| then take 1/result.
Shape of the loop
if n < 0: x, n = 1/x, -n
result = 1
while n > 0:
if n is odd: result *= x
x *= x # square the base
n = n // 2 # halve the exponent
return resultPseudocode only — the full worked solution lives in the Solution tab.
Easy way to go wrong
Integer overflow for n = -2^31 — |n| overflows int32. Handle this edge case with long/BigInt.