Trailing Zeros
Trailing Zeros (leetcodelintcode)
Description
Write an algorithm which computes the number of trailing zeros in n factorial.
Example
11! = 39916800, so the out should be 2
Challenge
O(log N) time
解题思路
正整数 n 的阶乘有多少个尾随零，可以用以下公式求解：
其中，k需要满足5^(k+1) > n。
可以进一步简化为更容易实现的以下形式：
定义q_i = n / (5^i)，初始状态为q_0 = n，迭代公式为q_i+1 = q_i / 5。
Java 实现
class
Solution
{
/*
* param n: As desciption
* return: An integer, denote the number of trailing zeros in n!
*/
public
long
trailingZeros
(
long
n)
{
if
(n
<
=
0
) {
return
0
;
}
long
sum =
0
;
while
(n !=
0
) {
sum += n /
5
;
n /=
5
;
}
return
sum;
}
}