# 7ms Java solution

• if a^k % m = a^t % m, then a^(k+1) % m must be equal to a^(t+1).
Let's say a^14 %m = a^27 %m, then a^28 % m is equal to a^15%m,
a^k %m = a^(k-13)%m.

let's have an array to keep the power of 'a' and the index is mod value, example:
a=2, b=0, modToPower[1] = 0;
a=2, b =1, modToPower[2] = 1;
a=2, b =2, modToPower[4] = 2;
...
the length of modToPower is 1337(it can be extended to any other positive integer).
and once there is b=x, and modToPower[a^b%1337] is existing, then we can exit the loop.

regarding array 'b', like above if a^k % m = a^(k-13)%m, we can easily map the value represented by array 'b' to mod by 13.
like a^[1,2,3] = a^123 = a^110 =...= a^6;

``````public int superPow(int a, int[] b) {
if (a <= 0 || b == null || b.length == 0) {
return 0;
}
int modNum = 1337;
a %= modNum;
int[] log = new int[modNum];
for (int i = 0; i < log.length; i++) {
log[i] = -1;
}
int startNum = 1;
Map<Integer, Integer> powerToModNum = new HashMap<Integer, Integer>();
int powerMod;
for (int startIndex = 0; ; startIndex++) {
startNum %= modNum;
if (log[startNum] == -1) {
log[startNum] = startIndex;
powerToModNum.put(startIndex, startNum);
startNum = (startNum*a)%modNum;

} else {
powerMod = startIndex - log[startNum%modNum];
break;
}
}

int j = 0;
for (int power : b) {
j = (j*10 + power%powerMod)%powerMod;
}
return powerToModNum.get(j);
}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.