设计一个算法，计算出n阶乘中尾部零的个数

样例

11! = 39916800，因此应该返回 2

看到题目首先想到的是计算n的阶乘然后再统计结果尾部零的个数

class Solution:    """    @param: n: An integer    @return: An integer, denote the number of trailing zeros in n!    """    def trailingZeros(self, n):        temp=n        for i in range(1,n):            temp=temp*i        Str=str(temp)        Zeros=0        for j in range(len(Str)-1,-1,-1):            if Str[j]=='0':                Zeros+=1            else:                break        return Zeros        # write your code here, try to do it without arithmetic operators.

但提交此代码之后，提示时间超限，只通过了百分之49的测试数据

发现当数据量很大的时候，计算开销会非常大

 

重新分析

1、2、3、4、5、6、7、8、9、10、11、...

1、分析上面的数列可知，每5个数中会出现一个可以产生结果中0的数字。把这些数字抽取出来是：

...、5、...、10、...、15、...、20、...、25、...

这些数字其实是都能满足5*k的数字，是5的倍数。统计一下他们的数量：n1=N/5。比如如果是101，则101之前应该是5,10,15,20,...,95,100共101/5=20个数字满足要求。

2、将1中的这些数字化成5*(1、2、3、4、5、...)的形式，内部的1、2、3、4、5、...又满足上面的分析：每5个数字有一个是5的倍数。抽取为：

...、25、...、50、...、75、...、100、...、125、...

而这些数字都是25的倍数（5的2次幂的倍数），自然也都满足5*k的要求。 

这些数字是25、50、75、100、125、...=5*(5、10、15、20、25、...)=5*5*(1、2、3、4、5、...)，内部的1、2、3、4、5、...又满足上面的分析，因此后续的操作重复上述步骤即可。 

统计一下第二次中满足条件的数字数量：n2=N/5/5，101/25=(101/5)/5=4。 

因为25、50、75、100、125、...它们都满足相乘后产生至少两个0，在第一次5*k分析中已经统计过一次。对于N=101，是20。因此此处的5*5*k只要统计一次4即可，不需要根据25是5的二次幂统计两次。 

后面的125,250,...等乘积为1000的可以为结果贡献3个0的数字，只要在5*5*k的基础上再统计一次n3=((N/5)/5)/5即可。 

class Solution:    """    @param: n: An integer    @return: An integer, denote the number of trailing zeros in n!    """    def trailingZeros(self, n):        temp=int(n/5)        Zeros=0        while(temp!=0):            Zeros+=temp            temp=int(temp/5)        return Zeros