Fast Power Algorithm

There is a leetcode problem Pow(x, n). Basically, it is a plain power function.

We can follow the description and multiple number x with n times.

function myPow(x: number, n: number): number {
    // for negative n, we need to do a 1/x operation
    if (n < 0) {
        n = -1 * n;
        x = 1 / x;
    }

    let ans = 1;
    for (let i = 0; i < n; i++) {
        ans *= x;
    }
    return ans;
};

As you can see, in this way, the time complexity is O(n).

We can use a divide and conquer approach to make the time complexity O(log(n)).

The idea behind this algorithm is based on the ideas below.

If number n is even, then we can have:

x^n = x^(n/2) * x^(n/2)

So with this idea, we can calculate x^n with only n/2+1 multiplication operations, instead of n times. (Suppose we do x^(n/2) with the brute-force approach).

If number n is odd, we can just minus 1 to make it even:

n = n - 1
x^n = x^(n/2) * x^(n/2) * x

So with this simple idea, let's see it in code.

function myPow(x: number, n: number): number {
    if (n < 0) {
        n = -1 * n;
        x = 1 / x;
    }

    if (n === 0) return 1;

    if (n % 2 === 0) {
        const v = myPow(x, n / 2);
        return v * v;
    } else {
        const v = myPow(x, (n-1) / 2);
        return v * v * x;
    }
};