题目：
设计一个算法，计算出n阶乘中尾部零的个数
11! = 39916800，因此应该返回 2
O(logN)的时间复杂度
解题：
通过直接求 1 到n 中5的个数 运行会超时。。。
维基百科中有如下计算方法：
Java程序：
class Solution {
/*
* param n: As desciption
* return: An integer, denote the number of trailing zeros in n!
*/
public long trailingZeros(long n) {
// write your code here
long count = 0;
for(long i=5;n/i>=1;i*=5){
count += n/i;
}
return count;
}
};
总耗时: 600 ms
时间好快的
Python程序：
class Solution:
# @param n a integer
# @return ans a integer
def trailingZeros(self, n):
count = 0
i = 5
while n/i>=1:
count +=n/i
i = i * 5
return count
总耗时: 98 ms
在维基百科下面还有下面的方法：
Java程序：
class Solution { /* * param n: As desciption * return: An integer, denote the number of trailing zeros in n! */ public long trailingZeros(long n) { // write your code here long q = n; long count = 0; while (q!=0){ count +=q/5; q = q/5; } return count; } };
总耗时: 583 ms
Python程序：
class Solution: # @param n a integer # @return ans a integer def trailingZeros(self, n): count = 0 p = n while p!=0: p = p/5 count +=p return count
总耗时: 104 ms
lintcode 容易题：Trailing Zeros 尾部的零
原文：http://www.cnblogs.com/theskulls/p/4875114.html