1. Negative exponent
A negative power is the reciprocal of the positive power.
if (n < 0) return 1 / fastPower(x, -n)Typorithm · medium
Fast Power
▷ Interactive algorithm labfast-powerdivide-and-conquerexponentiationhalvingrecursion
Saved on this device
Full lesson · 8 learning steps Open any exercise for focused practice
10%
Step 1 of 8 · intro card
Learn Fast Power
Divide & Conquer
Compute x^n in O(log n) by squaring x^(n/2), with one extra multiply for odd exponents.
Naive exponentiation multiplies x by itself n times, which is O(n).
Halving the exponent and squaring the result turns it into O(log n) multiplications.
An odd exponent needs one extra factor of x because integer division drops the remainder.
Preparing algorithm lab…
01
Compute x^(n/2) once, then square.
02
Odd n adds one extra x.
03
O(log n) multiplications.
function fastPower(x, n) {
if (n < 0) return 1 / fastPower(x, -n);
if (n === 0) return 1;
const half = fastPower(x, Math.floor(n / 2));
if (n % 2 === 0) {
return half * half;
}
return half * half * x;
}Read the implementation
Connect each part of the code to the concept before you type.
2. Base case
Any value raised to the zero power is one.
if (n === 0) return 13. Halve the exponent
Compute x to the n/2 once and reuse it.
const half = fastPower(x, Math.floor(n / 2))4. Even power
For even n, x^n is the square of x^(n/2).
return half * half5. Odd power
For odd n, multiply one extra x to account for the dropped remainder.
return half * half * xA complete learning loop
01
Understand
Read the concept map and follow the code breakdown.
02
Reconstruct
Type the implementation, repair mistakes and work through every recall exercise.
03
Verify
Use the final check without hints; revisit weak concepts in short practice sessions.