Simple factorial finding problem giving TLE

I was solving the example problem of dynamic programming at HackerEarth (here)

#include <iostream>
#define MOD 1000000007

using namespace std;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    long long int t, n;
    cin>>t;
    long long int ans = 1;
    while(t--){
        ans = 1L;
        cin>>n;
        for(long long int i = 2;i<=n;i++){
            ans = (ans*i)%MOD;
        }
        cout<<ans<<endl;
    }
    
    return 0;
}

Why is it giving me TLE?

Is my approach not of dynamic programming? I am saving my solution in just one variable “ans” as I don;t need more than that.

Simple answer is NO

See, what dynamic programming is using the values which are calculated earlier to store them in memory and than if we encounter them in future while computing we’ll call them from memory instead of computing them again. What you are doing is linearly calculating each and every value again and again.

Explanation on how to solve.

long long int fac[100000];

fac[0] = 1;
fac[1] = 1;

for(int i=2;i<100000;i++){
fac[i] = (i*fac[i-1])%mod;
}

now you can see, you are calculating each and every value factorial in only one traversal.

Hope this helps!

2 Likes
 "ans" as I don;t need more than that.

You need more than that.

Let me explain with an example.

T can be upto 10^5, meaning you might have to find factorial of 10^5 numbers.

Lets say i give you 10^5 first, then you will compute the factorial in O(N) time. Then I give you 10^5 -1, you will again take almost that much time. I then again give you 10^5. See the pattern? You are doing 10^5 operations per T, which is essentially 10^10 operations in worst case.

Dp would be if, you create an array arr[i], calculate factorial till 10^5 first, storing the ith factorial in arr[i], and then proceed to simply answer the queries in O(1) time. Input n and immediately print arr[n] (because we already calculated and stored the factorial before)

1 Like

Others have pointed out how to make your calculations fast, but still, you may get TLE, because you are flushing STDOUT with every endl. Hence, rendering fast io lines useless. You should use ‘\n’ instead of endl, and you will definitely see a performance improvement.

37sec difference XD

If I wasn’t able to make you understand than you can see my accepted solution

@vijju123 XD

1 Like

Excellent. Thanks, got the point. I was actually thinking it might have been the case that I need to remember for every number in a particular test case. It seems to be alike of those query problems. I think in that case a sorting of the queried numbers would make more sense.

Thanks for letting me know that.