Non-recursive, O(n) time complexity. (C++ Code with some hints)

• O(n) time complexity, where n is the length of b.

Some Hints:

• 1). There are at most 1337 (0~1336) possible results. So increasing b from 1 to an extreme large number, the same results will repetitively show up, as a loop. (What is the length of the loop?)
• 2). If the length of loop is c, then (a^b)%1337 = (a^(b%c))%1337.
• 3). If (a^b)%x = y, what is (a^(b+1))%x equal to? ------------------------------- (a*y)%x.
``````    // O(c): for this problem, c=1337, so...O(1).
int findLoopLength(long long a, long long c)
{
unordered_set<long long> unset;  // can also use array of length c
long long t = a%c;
while(unset.find(t)==unset.end())
{
unset.insert(t);
t = (t*a)%c;
}
return unset.size();
}

// return b%c
int bigMod(vector<int>&b, int c)
{
int p = 0;
for(auto d:b)
{
p = (p*10 + d)%c;
}
return p;
}

int superPow(int a, vector<int>& b) {
if(a==1) return 1;

int loop = findLoopLength(a, 1337);    // O(1)
int m = bigMod(b, loop);               // O(n), where n is the length of b

// costs no more than findLoopLength(...). If the results were stored during the process of finding loop length, this while-loop could be avoided.
long long r = a%1337;
while(m>1)
{
--m;
r = (r*a)%1337;
}
return r;
}
``````

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