how to reduce time taken

general
, ,
1

#include
using namespace std ;

/* run this program using the console pauser or add your own getch, system("pause") or input loop */

int main()
{
int t;
cin>>t;
while (t--)
{
int n ;
 unsigned long factorial = 1; 
int i;
cin>>n;
for(i=1;i<=n;i++)
factorial*=i;
cout<<factorial;
}
return 0 ; 
}
2

I think you were trying to solve this problem…

As limit of n here is 100… and numberOfTestCases can be upto 100… So use instead of calculating factorial again and again for each test case, you could first calculate factorial of all numbers till 100 and store it in some array and then for each test case just answer it from array where you have already stored all factorials.

Initially time complexity was O(nt) but after this it would be O(n+t).

Hope this will help… :slight_smile:

3

Hey @manavsethi1234,

you also can see the discussion here.

To reduce the time complexity of a factorial program, instead of calculating it, again and again, we can use memory. We will be storing answer of each factorial in a memory, if the answer is already found then it will directly fetch it from the memory otherwise change calculate it.

long long int fac[100000];

fac[0] = 1; fac1 = 1;

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

Hope this helps!

4

question link pls.