What is wrong with my code?


  • 0
    H

    My code is below, the idea is simple, status[i] maintains the number of combinations without A.

    class Solution {
    public:
        typedef long long int ll;
        ll mod_base = 1000000007;
        ll status[100001];
    
        ll calculate(int n){
            if(status[n] != (ll)(-1))
                return status[n];
            ll retV = calculate(n-2) % mod_base + calculate(n-3) % mod_base; 
            retV = retV % mod_base;
            retV += calculate(n-1) % mod_base;
            retV = retV % mod_base;
            status[n] = retV ;
            return retV;
        }
        int checkRecord(int n) {
            for(int i=0; i<100001; i++)
                status[i] = -1;
    
            status[0] = 1;
            status[1] = 2; //L or P
            if(n==1)
                return 3;
    
            status[2] = 4; //PP, LP, or PL or LL.
            status[3] = 7;
            ll retV = 0;
            for(int i=0; i<n; i++){
                retV += (calculate(i) * calculate(n-i-1)) % mod_base;
            }
            retV += calculate(n);
            retV = retV % mod_base;
            return retV;
        }
    };
    

    It will pass, n=100000 have result 749184020
    However, if I just slightly change logic to:

            ll retV = calculate(n-1) % mod_base + calculate(n-2) % mod_base; 
            retV = retV % mod_base;
            retV += calculate(n-3) % mod_base;
            retV = retV % mod_base;
    

    Leetcode will not pass and shows it fails in 100000.
    I dont see a difference. I run it locally and it works well.
    Thanks.


Log in to reply
 

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