C++ Simple O(n) solution 32ms


  • 0
    J
        int checkRecord(int n) {
            
            int m = 1000000007;
            
            // number of each type in previous layer
            int lastA = 1;
            int lastfirstL = 1; 
            int lastfirstAL = 0;
            int lastsecondL = 0;
            int lastsecondAL = 0;
            int lastP = 1; 
            int lastAP = 0;
            
            // number of each type in current layer
            int currentA;
            int currentfirstL; 
            int currentfirstAL;
            int currentsecondL;
            int currentsecondAL;
            int currentP; 
            int currentAP;
    
            for (size_t i = 0; i < n-1; ++i) {
                
                currentA = ((lastP + lastfirstL)%m + lastsecondL)%m;
                currentfirstL = lastP; 
                currentfirstAL = (lastA + lastAP)%m;
                currentsecondL = lastfirstL;
                currentsecondAL = lastfirstAL;
                currentP = ((lastfirstL + lastsecondL)%m + lastP)%m;
                currentAP = (((lastA + lastfirstAL)%m + lastsecondAL)%m + lastAP)%m;
                
                lastA = currentA;
                lastfirstL = currentfirstL; 
                lastfirstAL = currentfirstAL;
                lastsecondL = currentsecondL;
                lastsecondAL = currentsecondAL;
                lastP = currentP; 
                lastAP = currentAP;
            }
                
            return ((((((lastA + lastfirstL)%m + lastfirstAL)%m + lastsecondL)%m + lastsecondAL)%m + lastP)%m + lastAP)%m;
            
            
        }
    
    

Log in to reply
 

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