给定一个整数 n，返回 n! 结果尾数中零的数量。

示例 1:

输入: 3
输出: 0
解释: 3! = 6, 尾数中没有零。
示例 2:

输入: 5
输出: 1
解释: 5! = 120, 尾数中有 1 个零.
说明: 你算法的时间复杂度应为 O(log n) 。

首先想的是暴力列举

1
2
3
4
5
6
7
8
9
10
import math
def func(n):
    num = math.factorial(n)
    res = 0
    while(num>0):
        k = num%10
        if(k==0):
            res = res+1
        num = num //10
    return res

这样一来如果输入一个999之类的，绝对爆了时间复杂度，题目要求说时间复杂度要O(log n)，然后想到能产生0 的数就只有5为结尾的，5×2=10 25×4=100 125×8=1000 所以能不能数一下这个n!里面包含有多少个5和多少个2呢，一个一个数也不太现实，就想到了类似于素数筛的算法把2和5的倍数筛出来，代码如下

1
2
3
4
5
6
7
8
9
10
11
12
def func(n):
    num2=0
    num5=0
    i = 1
    while(pow(2,i)<=n):
        num2+=i
        i+=1
    i = 1
    while(pow(5,i)<=n):
        num5+=i
        i+=1
    return(min([num2,num5]))

后来一看，遇上10*9这样的，在pow()那一步就错了，emmm……

然后看题解，只需要将每个数字因式分解，找到2×5 的而个数即可，又因为2一定比5多，只需要找有多少个5即可，代码如下

1
2
3
4
5
6
7
def func(n):
    num = n
    res = 0
    while(num%5==0):
        res+=num//5
        num/=5
    return res