Shulou(Shulou.com)06/03 Report--

[topic description]

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

An algorithm is designed to calculate the number of trailing zeros in n-factorial.

[topic link]

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

[topic Analysis]

The traditional solution is to first find out the nails, and then calculate the number of the last zeros. (repeat / 10 until the remainder is not 0) the solution will lead to the overflow of factorial numbers when the input number is slightly larger.

O (logn) solution: a smarter solution is to consider n! The prime factor of the. The suffix 0 is always multiplied by prime factor 2 and prime factor 5. If we can count 2 and 5, the problem will be solved. Consider the following example:

N = 5: 5! The prime factor of (2 * 2 * 2 * 3 * 5) contains a 5 and three 2s. So the number of suffixes 0 is 1.

N = 11: 11! The prime factor of (2 ^ 8 * 3 ^ 4 * 5 ^ 2 * 7) contains two 5s and three 2s. So the number of suffixes 0 is 2.

It is easy to observe that the number of 2 in the prime factor is always greater than or equal to 5. So just count the number of five. So how to calculate n! What about the number of all five of the prime factors? A simple method is to calculate floor (nadir 5). For example, 7! There is a 5pm 10! There are two fives. In addition, there is one more thing to consider. Numbers such as 25125 have more than one 5. For example, if we consider 28 percent, we get an extra 5, and the total of 0 becomes 6. It is also easy to deal with this problem, first for n / 5, remove all individual 5, then 25, remove extra 5, and so on.

[reference answer]

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

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.