Pow(x, n) | Engineering Interview Kit

Concept

LeetCode #50.
Problem: Implement pow(x, n), which calculates x raised to the power n ( $x^n$ ).

Input: x = 2.00000, n = 10
Output: 1024.00000

If you use the built in Math.pow(x, n) or x ** n, you will fail the interview. You must write the engine yourself.

The Brute Force Approach ( $O(N)$ )

The mathematical definition of $2^{10}$ is 2 * 2 * 2... ten times.
You could just run a for loop $N$ times, multiplying the base number.

function brutePow(x: number, n: number): number {
    let result = 1;
    for (let i = 0; i < n; i++) {
        result *= x;
    }
    return result;
}

This is $O(N)$ time. What if n is 2.14 Billion? The loop will run 2 Billion times and trigger a Time Limit Exceeded error. We must do better.

The Optimal Approach: Binary Exponentiation ( $O(\log N)$ )

Instead of multiplying $2 \times 2$ ten separate times, we can exploit the mathematical laws of exponents.

The Math: $X^N = (X^2)^(N / 2)$
$2^{10} = (2^2)^5 = 4^5$ .
Notice what just happened. By squaring the base (2 -> 4), we instantly cut the exponent perfectly in half (10 -> 5)!
We mathematically skipped 5 loop iterations!

What if the exponent is Odd? (e.g., $4^5$ ). We cannot perfectly cut 5 in half.
We just peel off exactly one copy of the base and save it to our result, leaving an Even exponent!
$4^5 = 4 \times 4^4$ .
Now that it’s $4^4$ , we square the base again! $4^4 = (4^2)^2 = 16^2$ .

Because we are dividing the exponent in half at almost every single step, this algorithm executes in lightning fast $O(\log N)$ time. pow(2, 2_000_000_000) finishes in exactly 31 operations instead of 2 Billion!

Implementation

// Time Complexity: O(log N)
// Space Complexity: O(1)

function myPow(x: number, n: number): number {
    // Edge Case: Any number to the power of 0 is 1.
    if (n === 0) return 1;

    // Handle Negative Exponents (2^-3 is mathematically 1 / 2^3)
    let exponent = n;
    let base = x;
    
    if (exponent < 0) {
        base = 1 / base;
        exponent = -exponent;
    }

    let result = 1;

    // Run until the exponent is exhausted down to 0
    while (exponent > 0) {
        
        // Is the exponent Odd?
        if (exponent % 2 !== 0) {
            // Peel off one copy of the base and multiply it into our result
            result = result * base;
            
            // Subtract 1 to make the exponent perfectly Even
            exponent = exponent - 1;
        }

        // The exponent is now guaranteed to be Even.
        // Square the base!
        base = base * base;
        
        // Cut the exponent perfectly in half!
        exponent = exponent / 2;
    }

    return result;
}

The Bitwise Optimization

You can write this exact algorithm using pure Bit Manipulation to make it even faster!

Instead of checking exponent % 2 !== 0, you check (exponent & 1) === 1.
Instead of exponent = exponent / 2, you shift the bits exponent >>> 1.

Because Bit Shifting inherently forces numbers downward and ignores decimals, you don’t even need the exponent = exponent - 1 step! The >>> shift just effortlessly lops off the odd 1 bit and halves the number perfectly in a single clock cycle.

Interview Questions

Q: In the Negative Exponent handler, what happens if n is -2,147,483,648 (The absolute minimum 32-bit Signed Integer)?
A: This is a famous edge case that crashes many C++/Java solutions!
The maximum positive 32-bit integer is 2,147,483,647. (Notice it is 1 smaller than the negative max).
If you do exponent = -exponent, the math tries to convert -2,147,483,648 into positive 2,147,483,648. Because this positive number is physically too large to fit in a 32-bit signed integer, it triggers an Integer Overflow and instantly wraps right back around to a massive negative number! The while (exponent > 0) loop will never run.
In JavaScript, this is not a problem because all numbers are 64-bit Floats, but you must verbally point out this Integer Overflow trap to your FAANG interviewer.