Time limit 2000/4000/4000/4000 ms. Memory limit 65000/65000/65000/65000 Kb.
Prepared by Ibrahim Mesecan.
The number of Ending Zeros in n!
In Mathematics n! means the product of the numbers 1 through n. That is
5! = 1x2x3x4x5=120 and it has just 1 ending zeros.
7!=5040 again has just 1 ending zero.
10!=3628800 has 2 ending zeros.
In a number, ending zeros can be calculated by counting the number of (2x5) pairs in the factorized form of the number.
Hence, 300 has 2 ending zeros; 300 = 3 x (2x5) x (2x5). Because, there will be more 2s than 5s in n!, the number
of 5s will give the number of ending zeros.
The number of 5s (and hence the number of ending zeros) can be calculated with this algorithm.
Every number that is divisible by
- 5 will have at least one 5 in it; like 5, 10, 15, etc.
- 25 will have at least two 5s in it; like 25, 50, 75, etc.
- 125 will have at least three 5s in it; like 125, 250, 375, etc.
Question:
Write a program that is going to find out the number of ending zeros in n!
Input specification
You will be given one integer (n) which is 1 ≤ n ≤ 100.000.
Output specification
Give just one number that represent the number of ending zeros in n!
Sample Input I
1000
Sample Output I
249
|
Sample Input II
789
Sample Output II
195
|
Output Explanation :
res =1000 / 5 = 200 ==> there are 200 numbers that have at least one 5,
res =1000 / 25 = 40 ==> there are 40 numbers that have at least two 5s,
res =1000 / 125 = 8 ==> there are 8 numbers that have at least three 5s,
res =1000 / 625 = 1 ==> there is 1 number that has four 5s,
res =1000 / 3125 = 0 ==> there is 0 number that has five 5s,
The answer is sum of the results 200 + 40 + 8 + 1 = 249
Для отправки решений необходимо выполнить вход.
|