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