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


  • 1
    T

    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;
        }
    

Log in to reply
 

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