LeetCode数学篇：172.阶乘后的零

好多天没有更新了，四月要勤快起来。

一、题目

链接：https://leetcode-cn.com/problems/factorial-trailing-zeroes/

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

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

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

二、题解

2.1 因式分解

暴力方法就是我们算出数字的阶乘结果，最后统计末尾有多少个 0，如果数字很小的话还行，但是如果数字很大的就会溢出，所以我们需要更换下思路。

首先，让我们反向思考一下，题意是要求末尾有多少个 0，而每当末尾多一个 0 ，相当于我们给当前数字乘以一个 10。所以末尾有多少个 0，只需要给当前的数字乘以一个 10，是不是就这么简单。

现在，让我们以 6! 来举个例子：

6! = 6 * 5 * 4 * 3 * 2 * 1 = 720

我们发现结果有一个 0，说明有一个 10，其原因是因为 2 和 5 相乘构成了一个 10。而对于 10 的话，我们发现只有 2 * 5 可以构成 10，所以我们离真相更近一步了，我们只需要找有多少对 2 和 5。

现在，我们再以 12！来举例：

12! = 12 * 11 * 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 = 11 * (2 * 5) * 9 * (4 * 2) * 7 * (3 * 2) * (1 * 5) * (2 * 2) * 3 * (1 * 2) * 1


含有 2 的因子是 1 * 2, 2 * 2, 3 * 2, 4 * 2, 5 * 2

含有 5 的因子是 1 * 5, 2 * 5

这时我们发现，含有 2 的因子每两次出现一次，含有 5 的因子每五次出现一次，所以 2 的个数远远多于 5。所以，其实我们只要找到一个 5，一定可以找到一个 2 与之配对。最后的方案就变成了，只需要找有多少个 5，而不再需要找 10。

所以，很简单的方法就是用二重循环，直接判断每个数字是否能被 5 整除，如果可以的话就增加一个 0，不行的话直接跳出当前循环。

时间复杂度：O(nlogn)

空间复杂度：O(1)

class Solution:
    def trailingZeroes(self, n: int) -> int:
        count=0
        for i in range(n+1):
            tmp=i
            while tmp>0:
                if tmp%5==0:
                    count+=1
                    tmp//=5
                else:
                    break
        return count

2.2 因式分解优化

来来来，我们继续分析。上面代码的时间复杂度是 O(nlogn)，是不符合题意的，同时在 LeetCode会出现超时，所以我们需要优化一下。

• 经过上面的分析，我们可以看出对于一个数的阶乘，5 的因子一定是每隔 5 个数出现一次，如下：

n! = 1 * 2 * 3 * 4 * (1 * 5) * ... * (2 * 5) * ... * (3 * 5) *... * n

• 因为每隔 5 个数出现一个 5，所以计算有多少个 5，我们只需要用 n//5 就可以计算出来，但是还有以下情况：

... * (1 * 5) * ... * (1 * 5 * 5) * ... * (2 * 5 * 5) * ... * (3 * 5 * 5) * ...

• 通过上面的式子我们可以发现，每当隔 25 个数字时，出现的不再是一个 5，而是两个 5，所以除了每隔 5 个数算作一个 5，每隔 25 个数，还需要再多算一个 5，所以我们需要再加上 n 25 个 5。

• 同理我们还会发现每隔 5 * 5 * 5 = 125 个数字，会出现 3 个 5，所以我们还需要再加上 n 125 个 5。

• 所以，规律也就出来了，每隔 5 个数，出现一个 5，每隔 25 个数，出现 2 个 5，每隔 125 个数，出现 3 个 5，以此类推。

5 的个数就是 n 5 + n // 25 + n // 125 + ...

这时，我们可以把分析结果转换为 code 了，但是让我们仔细观察上面的公式，我们会发现分母是递增的，如果数字足够大的话，分母可能就会溢出，所以当我们计算 n//5，n//25，n//125 的时候，我们先更新 n，n = n//5，之后再计算 n//5。

时间复杂度：O(logn)

空间复杂度：O(1)

class Solution:
    def trailingZeroes(self, n: int) -> int:
        count=0
        while n>0:
            count+=n//5
            n//=5
        return count

这篇文章的思路是我之前在网上看见的，所以应该不算原创，很久之前留了个笔记，今天把笔记润色加工了，但是我已经记不得出处是哪里了。如有雷同，可联系我，谢谢。