can some one find a way to solve this problem. http://www.codechef.com/problems/EMA01. the problem constraints are not given clearly.let us assume that the input is less than 10^5.Assuming this can the problem be solved within the time constraint of 1 sec??
The problem seems broken.
The same problem is given here:
FCTRL
To have a trailing zero u need a multiple of 5 and a multiple of 2 in the factorial.
Since multiples of 2 occurs more frequently we just need to count the no. of multiples of 5 in n! which is equal to n/5
Similarly we need to find multiples of 25,125,625,etc for 2,3,4 trailing zeros respectively.
Thus solution = n/5 + n/125 + n/625 + … till n/x = 0
You can refer my solution: here
no this is the common misconception everyone attempting this problem fall prey to. In the problem statement it is clearly given that you need to find the total no of zeros ,not the total no of trailing zeros.hence if the factorial is say,11001000 then the answer must be 5 ,not 3. The algorithm you have specified above is for calculating the no of trailing zeros not the total zeros.
Sorry about that, i read it later.Still the problem is broken.I tried my python code but its giving runtime error and only possibilities for the error are inconsistent test data or n > 10^10.
I am using naive approach of finding the factorial and then counting '0’s and it runs in less than 1 sec for n < 10000. Also i don’t think there is any algorithm which can get you the intermediate zeros.I searched online the best i could find was an approximation algorithm.
i had also applied the same approach of finding the factorial and finding the zeros before posting this question,but is not time effective and is not getting accepting in codechef(time limit exceeded).and also no editorial exists for this question and no succesful submission also exists,and hence i was just curious to find out if any better way of solving this prob exists!!!