# Java solution, Pigeonhole principle.

• The idea is to find a cycle in the power. As the number is modded by 1337, there must be a duplication among the power of from 1 to 1337. This tells which position in cycle b corresponds to.

``````public int superPow(int a, int[] b) {
int []pows = new int[1337];    // max cycle is 1337
Set<Integer> set = new HashSet<Integer>();

// pigeon hole principle dictates that must be a duplicate among the power from 1 to 1337 if moded by 1337
int cycle = 0;
int val = 1;
for (int i = 0; i < 1337; i++)  {
val = (int)(((long)val * a) % 1337);
// cycle found
if (set.contains(val)) break;
pows[cycle++] = val;
}

// b: String -> BigInteger
StringBuilder str = new StringBuilder();
for(int v: b) str.append(v);
BigInteger bVal = new BigInteger(str.toString());

bVal = bVal.subtract(new BigInteger("1")).mod(new BigInteger("" + cycle));
return pows[bVal.intValue()];
}``````

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