Code-:CodeChef: Practical coding for everyone
Question-:FCTRL Problem - CodeChef
anyone?
There’s an easier way to do this.
The number of trailing zeroes at the end of N! is simply the highest power of 5 that divides N! (think why).
Code to refer later
#include <bits/stdc++.h>
using namespace std;
void solve() {
int n = 0;
cin >> n;
int ans = 0;
while(n >= 5) {
ans += n / 5;
n /= 5;
}
cout << ans << '\n';
}
int main() {
int t = 0;
cin >> t;
for(; t > 0; t--) {
solve();
}
return 0;
}
1 Like
But can you tell me my mistake in the code?
You are trying to calculate the factorial of N. Remember that N can be as large as 10^9.
Few examples of factorials
1 1
2 2
3 6
4 24
5 120
6 720
7 5040
8 40320
9 362880
10 3628800
11 39916800
12 479001600
13 6227020800
14 87178291200
15 1307674368000
16 20922789888000
17 355687428096000
18 6402373705728000
19 121645100408832000
20 2432902008176640000
21 51090942171709440000
22 1124000727777607680000
23 25852016738884976640000
24 620448401733239439360000
25 15511210043330985984000000
26 403291461126605635584000000
27 10888869450418352160768000000
28 304888344611713860501504000000
29 8841761993739701954543616000000
30 265252859812191058636308480000000
31 8222838654177922817725562880000000
32 263130836933693530167218012160000000
33 8683317618811886495518194401280000000
34 295232799039604140847618609643520000000
35 10333147966386144929666651337523200000000
36 371993326789901217467999448150835200000000
37 13763753091226345046315979581580902400000000
38 523022617466601111760007224100074291200000000
39 20397882081197443358640281739902897356800000000
40 815915283247897734345611269596115894272000000000
41 33452526613163807108170062053440751665152000000000
# That's around 50 digits.
Factorials grow extremely fast. You cannot even fit the factorial of 25 in an integer. How do you expect factorial of 10^9 to do so.
Even if it does (for big integers), you are using an O(N) loop to calculate factorial. This will time out for N larger than 10^8.
2 Likes
Here’s the thing - you’re calculating the factorial of the number followed by calculating the number of zeroes in the end. Sure, that sounds logical… Except when you take into account the fact that computers are weird when it comes to things that humans find intuitive.
An unsigned long long integer can have a value between 0 to 2^64 (-(2^63) to 2^63 - 1 for signed long long int). This range is enough for n (the value you’ll be given in the question). But things go south when you calculate the factorial of n. Look at the factorials of a few possible values of n less than or equal to 10:-
1! = 1
2! = 2
5! = 120
10! = 362880
See the sudden jumps in the value? Imagine how big it’ll get when n is around 10^9. That value can never be stored in a long long int. That’s why you would be getting a WA - the correct values of the factorials are never being calculated.
Let’s assume that there is some way to hypothetically store the value of the factorial of huge numbers. Here’s another problem - the time complexity, which happens to be linear (for the factorial function). That means, the time taken to compute the answer is directly proportional to the value of n. And when n is around 10^9 for a certain test case, your code will take a lot of time to calculate the answer and will give you a TLE.
^ This last paragraph was the primary issue with your code - it was taking too much time to calculate the answer. But regardless of this, you would have had the integer overflow issue.
As @suman_18733097 mentioned, there is a less intuitive but more efficient way of solving this, based on the highest power of 5. You can refer to the solution in their answer.
It’s awesome that you noticed the possible values of n in the question, which happened to be 10^9 - because of which I assume that you used a long long int instead of a regular int (if not, now you know!).
This whole thing is what makes competitive programming interesting. This was a math question, rather than a programming one; and the key to solving this was to make that observation related to the highest power of 5. A considerable subset of competitive programming questions is like this - making some sort of key observation.
Cheers 
Thank you for helping me and clearing my doubts 
Now I got it , Thanks