[title description]

Write an algorithm which computes the number of trailing zeros in n factorial.

Design an algorithm that calculates the tail number of zero in the n factorial,

[title link]

http://www.lintcode.com/en/problem/trailing-zeros/

[title]

The traditional method is first to find the n! The end, and then calculate the number of 0, repeat present 10 until the remainder non-zero) when the solution in the input Numbers larger overflow, will cause the factorial counting paltrily,

O (logn) solution: a smarter is to consider the solution to the n! Prime factors, suffix 0 always by the qualitative factor 2 and qualitative factor is multiplied by 5, and if we can count the number of 2 and 5, problem solved, consider the following example:

N=5:5! The qualitative factors (2 * 2 * 2 * 3 * 5) contains a three 2, 5, and therefore the suffix number is 1, 0

N=11:11! The qualitative factors (2 ^ 8 * 3 5 ^ ^ 4 * 2 * 7) contains two three 2, 5, and so the suffix number is 2, 0

It is easy to observe the number of qualitative factor of 2 is always greater than or equal to the number of 5, so just count the number of 5, so how to calculate n! The number of the qualitative factor in all 5? A simple method is to calculate floor (n/5), for example, seven! There is a 5, 10! Two 5, in addition, there is one thing to consider, such as 25125 Numbers have more than one 5, for example, if we think about 28! , we get an extra 5, and the total number of 0 to 6, it's also simple to deal with this problem, first of all n present 5, remove all single 5, 25, and then present to remove the extra 5, by analogy,

[the reference answer]

http://www.jiuzhang.com/solutions/trailing-zeros/