I’ve provided both top down and top up solutions to this problem. “Top down” is a divide and conquer algorithm, recursive implementation. “Top up” uses the binary decomposition of exponentials.

Approach 1: Divide and conquer (think top down)

Our goal is to lower the index, so we can split the problem until we can’t, passing the results up layer by layer. Here is a schematic for calculating 272^727.

Reference code 1:

public class Solution {

    public double myPow(double x, int n) {
        long b = n;
        if (n < 0) {
            return 1 / myPow(x, -n);
        }
        return myPow(x, b);
    }

    private double myPow(double x, long n) {
        if (n == 0) {
            return 1;
        }
        if ((n % 2) = =1) {
            return x * myPow(x, n - 1);
        }
        return myPow(x * x, n / 2); }}Copy the code

Method two: bottom up

When the exponent is negative, you can convert it to the inverse of the base, the inverse of the exponent, which is not hard to understand.

In order to avoid multiplying the bases over and over again, we use the lazy strategy of, say, 5185^{18}518, instead of doing 999 times 5\times 5×5, we just have to figure out 595^959 and then multiply it by ourselves.

One way to find a proper “decomposition” of an integer is to think of an integer as its binary form. In the example above, the binary representation of 181818 is (10010)2(10010)_2(10010)2, which is:


18 = 1 x 2 4 + 1 x 2 1 18 = 1 \times 2^4 + 1\times2^1

So:


5 18 = 5 2 4 x 5 2 1 5^{18} = 5^{2^4} \times 5^{2^1}

Thus, we can “binary decompose” the exponent NNN, preserving the required part of the final result as the base is constantly multiplied by itself.

Reference code 2:

public class Solution {

    public double myPow(double x, int n) {
        // Note the type conversion here
        // Respond to the -2147483648 use case
        long b = n;
        if (n < 0) {
            x = 1 / x;
            b = -b;
        }

        double res = 1.0;

        while (b > 0) {
            if ((b % 2) = =1) {
                res *= x;
            }
            x *= x;
            b >>= 1;
        }
        returnres; }}Copy the code