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

样例

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

挑战

O(logN)的时间复杂度

思路

思考一个数尾部的零是怎么得来的，乘以10对吧，所以n的阶乘尾部有多少零就可以看成它有多少个10这个因子，而10又可分解为两个质因数相乘 2×5 。将 n!分解为质因数相乘的形式，大概是这样：

n!=1×2×3×(2×2)×5×(2×3)×7×(2×2×2)×(3×3)×(2×5)...

显然，2的个数会比5的个数多，所以有多少个5就会有多少个10。故而问题就转化为寻找 n! 的结果有多少个5这个因子。

那么这个怎么找呢？我们看一下上边的等式，现在已经乘到10了，出现了2个5，想象一下继续乘下去的情况，到15时会再出现一个，到20时又会再出现一个，到25时则会出现2个，继续看下去，就会发现一个规律：

(1) 每逢遇到5的倍数，就会出现一个;

(2) 每逢遇到5的幂次方的倍数，就会出现5的幂次方的指数个，为了便于计算，我们把遇到5的幂次方的倍数时也算到5的倍数里，这时遇到5的幂次方的倍数就会出现(5的幂次方的指数-(5的幂次方的指数-1))个，也就是1个。

这样用文字来说会有点绕，我们不妨用代数式说明一下：

5 的倍数，遇到一次就出现1个5，会遇到n/5 次，记作n/5 × 1 = n/5 个；

5^2 的倍数，遇到一次就会出现2个5，会遇到n/5^2 次，但是 5^2 的倍数又包含在 5 的倍数中，所以如果我们按2个算就会每次遇到都多计算1次，因此把那1次减去，就记作 n/5^2 ×(2−1) 个；

5^3 的倍数，遇到一次就会出现3个5，会遇到 n/5^3 次，但是 5^3 的倍数又包含在 5 的倍数和 5^2的倍数中，所以如果我们按3个算就会每次遇到都多计算2次，因此把那2次减去，就记作 n/5^3 ×(3−2) 个；

5^4 的倍数，同理，可记作 n/5^4 ×(4−3) 个；

依此类推下去。

根据以上，我们不难得出一个公式：

Sum=n/5+n/5^2+n/5^3+n/5^4+···

有了这个公式，问题就容易了，只需求出 log5n，取整，然后将其作为循环次数累加就行了。

class Solution:

"""

@param: n: An integer

@return: An integer, denote the number of trailing zeros in n!

"""

def trailingZeros(self, n):

count = 0

p = n

while p!=0:

p = p//5

count +=p

return count

# write your code here, try to do it without arithmetic operators.

class Solution:

"""

@param: n: An integer

@return: An integer, denote the number of trailing zeros in n!

"""

def trailingZeros(self, n):

count = 0

i = 5

while n / i >= 1:

count += n // i

i = i * 5

return count

# write your code here, try to do it without arithmetic operators.