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.
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.
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)
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.
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.