Super Pow

Problem

Your task is to calculate ab 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

Analysis

My original solution, parseLong() won't work if array is too big

public class Solution {
    public int superPow(int a, int[] b) {
        StringBuilder sb = new StringBuilder();
        for (int num : b) sb.append(num);
        long pow = Long.parseLong(sb.toString());
        long res = 1;
        if (pow == 0) return (int) res;
        while (pow-- > 0) res *= a;
        return (int) (res % 1337);
    }
}

Accepted Solution: O(n) time

public class Solution {
    public int superPow(int a, int[] b) {
        return superPow(a, b, b.length, 1337);
    }

    private int superPow(int a, int[] b, int length, int k) {
        if (length == 1) return powMod(a, b[0], k);
        return powMod(superPow(a, b, length - 1, k), 10, k) * powMod(a, b[length - 1], k) % k;
    }

    //Helper method to get x ^ y mod k
    private int powMod(int x, int y, int k) {
        x %= k;
        int res = 1;
        while (y-- > 0) {
            res = (res * x) % k;
        }
        return res;
    }
}

Analysis

In the O(n) solution, we use the formula below:
mn % k = (m % k) * (n % k) % k
Then we have another observation:
a ^ 1234567 % k = (a ^ 1234560 % k) * (a ^ 7 % k) % k = (a ^ 123456 % k)^ 10 % k * (a ^ 7 % k) % k
We follow these formulas to simply our calculation process and get final result
Not that hard as long as you apply the formulas huh