Time limit exceed error at Factorial ques.

general
1

Can someone please help me out.
My question is

And here is my solution,

#include
#include<stdio.h>

using namespace std;

int main()
{
int n,c=0;
scanf(“%d”,&n);
int no[n],zero[n];
int i;long p;
for(i=0;i<n;i++)
{
scanf(“%d”,&no[i]);
//factorial finding
for(int j=1;j<=no[i];j++)
{
p=p*j;
}
//finding the number of zero at the end of the factorial
while(p!=0)
{
if(p%10==0)
c++;
p/=10;
}
zero[i]=c;
c=0;p=1;
}
//printing
printf(“\n%d”);
for(i=0;i<n;i++)
printf(“%d%”,&zero[i]);
return 0;
}

The online judge is continously giving me Time out error. I cannot get mistake here. Can someone please point out it.

Thanks in advance.

2

Input specs says that 1 \leq N \leq 1000000000 \approx 10^9, but time limit is 8 seconds… modern computers can only compute around 10^8 operations per second, so this is pushing it. Moreover, there are about 100000 test cases, so it is no surprise that the solution will time out. Try doing something akin to fibonacci recurrence relations or prime factors to speed up your solution.

2 Likes
3

#include<bits/stdc++.h>
using namespace std;

int main() {
int t;
cin>>t;
while(t–)
{
long long n;
cin>>n;
long long ans=0;
long long k=5;
while(k<=n)
{
ans=ans+n/k;
k=k*5;
}
cout<<ans<<endl;
}
return 0;
}
we know that the number of zeros at the end can be found from min(power of 2,power of 5) present in a given number because 10=2x5; so which ever is min that will be the answer .say we have power of 2 as 6 and power of 5 as 3 then we get (2x5)^3 * 2^3 i.e 3 zeros at the end.