O(n) time and O(1) space solution


  • 0
    S
        public int checkRecord(int n) {
            if (n <= 0)
                return 0;
            if (n == 1)
                return 3;
            int A2L = 0, i;
            int A1L = 1;
            int AnoL = 3;
            int noA2L = 1;
            int noA1L = 1;
            int noAnoL = 2;
            int temp1,temp2, temp3,temp4,temp5,temp6;
            int remain = 1000000007;
            
            for (i=3;i<=n;i++) {
                temp1=A2L;temp2=A1L;temp3=AnoL;temp4=noA2L;temp5=noA1L;temp6=noAnoL;
                A2L = temp2;
                A1L = temp3;
                AnoL = (((((temp1 + temp2) % remain + temp3) % remain + temp4) % remain + temp5) % remain + temp6) % remain;
                noA2L = temp5;
                noA1L = temp6;
                noAnoL = ((temp4 + temp5) % remain + temp6) % remain;
            }
            return (((((A2L + A1L) % remain + AnoL) % remain + noA2L) % remain + noA1L) % remain + noAnoL) % remain;
        }
    }

Log in to reply
 

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