Super Pow

372. Super Pow

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  
public class Solution {  
    public int superPow(int a, int[] b) {
        int result = 1;

        for (int i = 0; i < b.length; i++) {
            result = pow(result, 10) * pow(a, b[i]) % 1337;
        }

        return result;
    }

    int pow(int x, int n) {
        if (n == 0) {
            return 1;
        }
        if (n == 1) {
            return x % 1337;
        }

        return pow(x % 1337, n / 2) * pow(x % 1337, n - n / 2) % 1337;
    }
}

Hope this helps,
Michael