题目描述
【leetcode】172. 阶乘后的零( Factorial Trailing Zeroes )
给定一个整数 n，返回 n! 结果尾数中零的数量。
说明: 你算法的时间复杂度应为 O(log n) 。
错误的思路1：
n!展开过程中，每次相乘时，尾数0的数量只与最后一位非0值有关，
所以每次相乘后累加末尾0的个数，然后只取最靠右的非0值。
这种想法是错的，反例 25*4=100，有2个0，若只考虑最靠右非0值，只能得到1个0
错误的思路2：
末尾0的数量即为1,2,3,…,n中因子5的个数，而因子5的个数即为下列数列和: int(n/5),int(n/52),...,int(n/5num) 。其中项数 num=int(lg(n)/lg(5)) ;
上面的数列似乎是等比数列前n项和的形式，但是请注意，其中每一项都带了int()，即向下取整，所以把它当作等比数列的画会引入误差积累，计算到某些输入值会出错，但是还是想讨论一下。
若不考虑int()带来的误差，则 Sn=a1(1−qn)/(1−q) ;，注意，由上面推导，Sn必定是整数，例如Sn=49。由于q=1/5为浮点数，导致Sn计算将导致误差，Sn可能为48.999，或者是49.0001。所以我们需要把Sn式子分子分母同乘以q^n，变形为无浮点数的运算， Sn=a1(5n−1)/(4∗5n−1) ;
错误的思路2的代码：
#include <cmath>
class Solution {
public:
int trailingZeroes(int n) {
if(0 == n)
return 0;
int num = log(n)/log(5);
int a1 = n/5;
// double q = 1/5.0;
// int count = a1*(1-1/pow(5,num))/(1-q) ;
int count = a1*(pow(5,num)-1)/(4*pow(5,num-1));
return count;
};
第一次解答
思路：阶乘n!中末尾0的数量 等于 阶乘n!中因子10的数量 进而等于 阶乘中因子2和因子5的成对出现的次数，因为因子2需要每递增2就至少新增一个，而因子5需要每递增5才至少出现一个，所以2的数量远比5的数量多，因此，又有阶乘n!中末尾0的数量 等于 阶乘n!中因子5的数量
到这里已经可以直接求解，但是若是遍历1-n去寻找所有因子5，时间复杂度为nlogn，能否有更简单的方法？答案当然是有。
通过观察可得出，阶乘n!中因子5的数量 即为下列数列和: int(n/5),int(n/52),...,int(n/5num)
其中，项数 num=int(log5(n)) 。请注意，其中每一项都带了int()，即向下取整，所以把它当作等比数列的画会引入误差积累，所以我们不能直接利用等比数列前n项和计算结果，需要用程序展开计算每一项，时间复杂度为log5(n)即O(log n)。
test case:
5
0
1
200
class Solution {
public:
int trailingZeroes(int n) {
int count = 0;
while(n>4){
n = n/5;
count += n;
}
return count;
}
};
结果：