C++ soln O(n) Soln ig


#1
int Solution::solve(int A) {
    
    if(A%2==1) return 0;
    
    int mod = pow(10,9)+7;
    
    long long int dp[A];
    long long temp = 0;
    dp[0] = 1;
    dp[1] = 3;
    for(int i=4;i<=A;i+=2){
       dp[(i/2)] = (3*dp[(i/2)-1])%mod;
       
       temp = (temp+(2*dp[(i/2)-2])%mod)%mod;
       
       dp[(i/2)] = (dp[i/2]+temp)%mod;
    
    }
    
    return dp[A/2];
    
    
}