I’ve just started learning C, and I know basics till loops. So I have tried doing this problem using what I know. Its working fine. And on my pc for n = 10^9 , it takes hardly 1 second to execute. Yet here when i submit, it says “Time Limit exceeded” . Am I taking the wrong meaning of time limit? I’m assuming time limit means the time to compute for the largest value of n. Can someone check my code, and tell me why its giving me that error? Thankyou.
here’s my code:
Algorithm: We need number of 5’s. So we can first start by seeing how many multiples of 5 are present in the factorial. eg: 100! contains 5,10,15,20…95,100. So twenty 5’s. Next we check how many multiples of 5^2 are present( for 100 there are 4, which are 25,50,75,100) these contain two 5’s each, but we have alread ycounted one 5 before. So we need to count [(power factor) - 1] number of 5’s, which in this case amounts to (2 - 1) for each . So we have 4*1=4 more 5’s. But 100 contains no 125’s(5^3). So total 5’s are 20 + 4 = 24, and thus 24 zeroes.
#include<stdio.h>
#include<math.h>
int main()
{
int i, j, p, n, a = 25, k = 1, z=0; /*i takes value of number of cases first, then switches to input number. j stores i to restore i after modification.p is a counter for number of cases. n is a counter that increments a which is pow(5,2) first then (5,3) etc. k is a multiplier( for a = 5^2, does 25*1, 25*2, 25*3..etc skips 25*5 as it will be included in 125*1, so skips all k%5=0 values.) z is the counter for number of 5's.*/
scanf("%d", &i);
j = i;
for(p = 1; i > 0; p++)
{
scanf("\n%d", &i);
for(n = 1; (5*n) <= i ; n++)
{
z++;
}
for(n = 2; (k * a) != 0; n++)
{
a = pow (5, n);
k = 1;
for(; (k * a) <= i ; k++)
{
if((k % 5) != 0)
{
z = z + n - 1;
}
}
k = k - 1;
}
printf("%d\n", z);
z = 0;
k = 1;
a = 25;
i = j;
i = i-p;
}
return 0;
}