Factorial problem

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;
}

Maybe istead of skipping common factors (which is a good idea btw) you can count all the unique factors, by using a function where you maintain a condition (like a while loop) over the powers of 5, and keep checking it until it is equal or larger than input value N.

At each time, to add up all the factors for a given power you can simply add the amount N/pow(5,i) to a counter and increment i by 1 afterwards… This way you will avoid unecessary work and hopefully your code will run faster :slight_smile:

Good luck

1 Like

The input for the factorial problem is a number T (max 100000), which denotes the number of values N that follow. The time limit indicates how long your program is allowed to use for the entire input (in this case at most 100000 N-values). 1 second for a single value N is too long, as it may take 100000 seconds to complete the input.

2 Likes

ill try that, thanks. But why does it give time exceeded right now? Its not taking more than 2 seconds for 10^(9) which is the max limit of n. Time limit mentioned is 8 seconds. what does time limit actually mean?

U need to Intend your code and place it in Code tags. Make it read-able!!

Small Thing: Y do u need to use pow function instead u can assign a variable with 5 initially and multiply it with 5 in each iteration!

Usually, the % operator is quite time consuming… That along with the use of SPOJ serves to run the programs, plus your use and change at runtime of several variables can cause you a TLE… The approach I suggested does not use the % operator and it’s more “clean” in the sense that it only uses 2 variables, along with the N we are to input…

Good luck

1 Like

okay got it , thanks :slight_smile: