LeetCode 50 — Pow(x, n) — Fast Exponentiation

What does it solve?

Implement pow(x, n) without multiplying x together n times (which would be O(N)). Instead, we use the identity:

xⁿ = (x²)^(n/2) if n is even
xⁿ = x · x^(n−1) if n is odd

This halves the exponent each time, giving O(log N) multiplications total. Negative exponents are handled by computing x^|n| and taking the reciprocal.

The core idea

// myPow(x, n):
if n == 0: return 1
if n < 0: x = 1/x; n = -n
half = myPow(x, n/2)
if n % 2 == 0:
return half * half
else:
return x * half * half

Complexity

Time complexity

O(log N)

The exponent is halved on every recursive call — depth of the call stack is ⌊log₂ N⌋ + 1, regardless of x.

Space complexity

O(log N)

Recursion stack depth equals the number of halvings. The iterative (binary exponentiation) variant brings this to O(1).

Examples & edge cases

Live animation — recursive fast exponentiation

Current call (descending) Returned (ascending) Active bit in exponent Used bit (odd branch)

Computing

—

x (current)

—

n (current)

—

Result

—

Call Stack (bottom = first call, top = deepest)

Binary representation of |n| — each set bit contributes a squaring

x = — n = — result = — depth = —

Step — of —

x (base)

—

n (exponent)

—

half²

—

Return value

—

Select an example and press Play to start.

✓ Complete

Speed Medium

Step-by-step table

Step	Phase	Depth	x	n	n even?	Action	Return value

C++ implementation

fast_power.cpp

#include <bits/stdc++.h>
using namespace std;

// Recursive — O(log N) time, O(log N) space
double myPow(double x, long long n) {
    if (n == 0) return 1.0;
    if (n < 0) { x = 1.0 / x; n = -n; }

    double half = myPow(x, n / 2);
    if (n % 2 == 0)
        return half * half;           // even: x^n = (x^(n/2))²
    else
        return x * half * half;      // odd:  x^n = x · (x^(n/2))²
}

// Iterative (binary exponentiation) — O(log N) time, O(1) space
double myPowIter(double x, long long n) {
    if (n < 0) { x = 1.0/x; n = -n; }
    double result = 1.0;
    while (n > 0) {
        if (n % 2 == 1) result *= x;  // odd bit → multiply in x
        x *= x;                         // square for next bit
        n /= 2;
    }
    return result;
}

int main() {
    cout << myPow(2.0, 10) << "\n";  // 1024
    cout << myPow(2.0, -3) << "\n"; // 0.125
    return 0;
}

My Notes

📝 Notes ✅

▼

● Start typing to save... 0 chars