Super Power

leetcode 372

Your task is to calculate a^b mod 1337 where a is a positive integer and b is an extremely large positive integer given in the form of an array.

Example1:

a = 2
b = [3]

Result: 8

Example2:

a = 2
b = [1,0]

Result: 1024

Solution is from here. Basically, it is all about a remainder multiplication rules. We have the conduction:

And we define a helper function: superPowHelper(int a, int[] b, int pos) means 

In this way, we have the code:

public static int superPowHelper(int a, int[] b, int pos) {
    if (pos <= 0) {
        return pow(a, b[0]);
    }
    int next = superPowHelper(a, b, pos - 1);
    return ((pow(next, 10) % DIV) * (pow(a, b[pos]) % DIV)) % DIV;
}

Besides, we need a normal power function which I wrote before:

public static int pow(int a, int b) {
    int ans = 1;
    while (b > 0) {
        if (b % 2 == 1) {
            ans = (ans * a) % DIV;
        }
        a = (a * a) % DIV;
        b = b >> 1;
    }
    return ans;
}

Check my code on github.