50. Pow(x, n)

Raise a floating-point base to an integer power without calling the built-in. The trick is binary (fast) exponentiation: square the base, halve the exponent, and absorb one extra factor whenever the exponent is odd — yielding O(log n) multiplications instead of O(n).

● MediumFast ExponentiationDivide & ConquerBit ManipulationTypeScript

PROBLEM What we're solving

Implement myPow(x, n) which computes x raised to the power n, where x is a float and n is a 32-bit integer (can be negative). For example: myPow(2, 10) → 1024, and myPow(2, -2) → 0.25. Calling x * x * … n times naively is too slow when n is large (up to ~2 billion).

KEY IDEA Write n in binary — each bit is a squaring step

Insight → every integer n can be expressed in binary. Reading the bits right-to-left: each bit position doubles the base (squaring), and when a bit is 1 we multiply that power into the result. So 2¹⁰ = 2² × 2⁸ — only two multiplications instead of nine. This is fast exponentiation, also called exponentiation by squaring.

RECIPE Square, halve, absorb

0 · Handle negative n. If n < 0, flip to x = 1/x and n = -n. Now we only deal with non-negative exponents.
1 · Initialise. result = 1, base = x, exp = n.
2 · Loop while exp > 0. Each iteration processes one binary bit of exp:
2a · Odd check. If exp % 2 === 1, multiply result *= base. This "absorbs" the factor for the current bit position.
2b · Square and halve. base = base * base (advance to the next bit position), exp = Math.floor(exp / 2) (shift bits right).
3 · Return result. All bits processed; result holds the answer.

Classic confusion → beginners flip the order — they halve first, then check parity. Always check exp % 2 before halving; otherwise you lose the low bit and multiply the wrong factors in.

COST Complexity & alternatives

Naive loop (x * x * … n times)

O(n)

n up to 2³¹ ≈ 2 billion — far too slow.

Fast exponentiation

O(log n)

O(log n) multiplications; O(1) space.

Recursive variant

The recursive form is elegant: pow(x,n) = pow(x*x, n/2) when n is even, x * pow(x*x, (n-1)/2) when odd. Stack depth is O(log n), which is fine but the iterative version uses O(1) space.

Pattern transfer → the same squaring trick appears in modular exponentiation (add % MOD to each multiply), matrix exponentiation (Fibonacci in O(log n)), and fast multiplication(Russian peasant algorithm). Recognising "repeat an operation n times" as a signal for binary decomposition is the key transfer.

RUN IT Square the base, halve the exponent

x =n =

step 0 / 9

STARTCompute 2¹⁰. Negative exponent? Invert x and negate n first.

1▶function myPow(x: number, n: number): number {
2  // Handle negative exponent: x^-n = (1/x)^n
3  if (n < 0) {
4    x = 1 / x;
5    n = -n;
6  }
7 
8  let result = 1;
9  let base = x;
10  let exp = n;
11 
12  // Fast (binary) exponentiation: O(log n)
13  while (exp > 0) {
14    if (exp % 2 === 1) {
15      result *= base;   // odd exponent: absorb one factor
16    }
17    base *= base;       // square the base
18    exp = Math.floor(exp / 2);  // halve the exponent
19  }
20 
21  return result;
22}

State

result

base (squaring)odd-bit: absorb factorisOdd = true (absorbing)result accumulator

slowfast

TYPESCRIPT The solution, annotated

myPow.ts
function myPow(x: number, n: number): number {
  // Handle negative exponent: x^-n = (1/x)^n
  if (n < 0) {
    x = 1 / x;
    n = -n;
  }

  let result = 1;
  let base = x;
  let exp = n;

  // Fast (binary) exponentiation: O(log n)
  while (exp > 0) {
    if (exp % 2 === 1) {
      result *= base;   // odd exponent: absorb one factor
    }
    base *= base;       // square the base
    exp = Math.floor(exp / 2);  // halve the exponent
  }

  return result;
}

Reading it block by block

Lines 2–4 — negative exponent. x⁻ⁿ = (1/x)ⁿ. Inverting x and negating n lets the rest of the function handle only non-negative exponents without any branching later.

Lines 6–8 — initialise accumulators. result starts at 1 (the multiplicative identity). base will be squared each iteration. exp is consumed bit-by-bit.

Lines 11–17 — the binary loop. Each pass reads the least-significant bit of exp. When that bit is 1 (odd check), the current power of the base is "on" in the binary decomposition of n, so we absorb it into result. Then we square base to advance to the next bit position and right-shift exp.

Line 19 — return. Once exp reaches 0, all bits have been processed and every contributing power of x has been folded into result.

Complexity → O(log n) time — the loop runs once per bit in n's binary representation. O(1) space — purely iterative with a fixed number of variables.

INTERVIEWFollow-ups they'll ask

"What about integer overflow for n = Integer.MIN_VALUE?" In languages with 32-bit ints, -n overflows when n is -2147483648. Use a BigInt or long cast before negating.
"Can you do it recursively?" Yes: pow(x, n) = pow(x*x, n/2) for even n, or x * pow(x*x, (n-1)/2) for odd. Stack depth is O(log n).
"Modular exponentiation?" Add % MOD after each multiply. Same loop structure; this is how cryptographic libraries compute aᵉ mod m efficiently.
"What if x = 0 and n = 0?" Mathematically ambiguous, but LeetCode defines 0⁰ = 1. The loop handles it correctly: exp = 0, loop doesn't execute, returns 1.
"Matrix exponentiation?" Replace scalar multiply with matrix multiply and you can compute Fib(n) in O(log n)— the same pattern, just with 2×2 matrices as the "base".

OPTIMAL Fast Exponentiation

myPow.ts
function myPow(x: number, n: number): number {
  // Handle negative exponent: x^-n = (1/x)^n
  if (n < 0) {
    x = 1 / x;
    n = -n;
  }

  let result = 1;
  let base = x;
  let exp = n;

  // Fast (binary) exponentiation: O(log n)
  while (exp > 0) {
    if (exp % 2 === 1) {
      result *= base;   // odd exponent: absorb one factor
    }
    base *= base;       // square the base
    exp = Math.floor(exp / 2);  // halve the exponent
  }

  return result;
}

Complexity → O(log n) time — the loop runs once per bit in n's binary representation. O(1) space — purely iterative with a fixed number of variables.

ALT 1 Brute force — multiply n times in a loop

O(n) time · O(1) space

The literal definition: xⁿ is x multiplied by itself n times. Handle a negative exponent by inverting the base first, then loop.

approach-2.ts
function myPow(x: number, n: number): number {
  if (n < 0) {
    x = 1 / x;
    n = -n;
  }

  let result = 1;
  for (let i = 0; i < n; i++) {
    result *= x;   // one factor per iteration
  }
  return result;
}

Note → With n up to ~2³¹, this runs billions of multiplications and times out. Because xⁿ = (x²)^(n/2), squaring the base while halving the exponent processes one binary bit of n per step, cutting the count from n to log₂ n.

MNEMONIC The one-liner

"Odd? Grab a copy. Always square and halve. Repeat until nothing's left."

TRIGGERS When you see _ → reach for _

"implement pow / exponentiation without built-in"	fast exponentiation loop
repeat-multiply n times (n large)	binary decomposition: O(log n)
negative exponent	invert base, negate exponent, proceed normally
"modular exponentiation / Fibonacci in log n"	same loop, swap scalar → matrix or % MOD

SKELETON The reusable shape

skeleton.ts
function myPow(x: number, n: number): number {
  if (n < 0) { x = 1 / x; n = -n; }
  let result = 1;
  let base = x;
  let exp = n;
  while (exp > 0) {
    if (exp % 2 === 1) result *= base;
    base *= base;
    exp = Math.floor(exp / 2);
  }
  return result;
}

FLASHCARDS Tap to flip

Core recurrence of fast exponentiation?

If exp is odd: result *= base. Always: base = base², exp = ⌊exp/2⌋.

tap to flip

1 / 7

Answer to reveal explanations. No penalty for retries.Score: 0 / 9

QUESTION 01

What is the time complexity of fast exponentiation for myPow(x, n)?

QUESTION 02

What is the very first thing to do when n is negative?

QUESTION 03

In the loop, the parity check exp % 2 === 1 must come _____ the halving step exp = Math.floor(exp / 2).

QUESTION 04

Trace myPow(2, 10). How many multiplications does the fast algorithm perform?

QUESTION 05

What does myPow(2, 0) return?

QUESTION 06

How would you adapt this algorithm for modular exponentiation (computing x^n mod M)?

QUESTION 07

The space complexity of the iterative fast exponentiation is:

QUESTION 08

#50 · Pow(x, n)Fast binary exponentiation: square the base and halve the exponent each step, handling the odd-exponent remainder. Invert the base for negative n. O(log |n|) multiplications.Which algorithmic approach does this primarily use?

QUESTION 09

PROBLEM What we're solving

KEY IDEA Write n in binary — each bit is a squaring step

RECIPE Square, halve, absorb

COST Complexity & alternatives

Recursive variant

RUN IT Square the base, halve the exponent

TYPESCRIPT The solution, annotated

Reading it block by block

INTERVIEWFollow-ups they'll ask

OPTIMAL Fast Exponentiation

ALT 1 Brute force — multiply n times in a loop

MNEMONIC The one-liner

TRIGGERS When you see ___ → reach for ___

SKELETON The reusable shape

FLASHCARDS Tap to flip

TRIGGERS When you see _ → reach for _