【面试经典 150 | 数学】阶乘后的零

写在前面

本专栏专注于分析与讲解【面试经典150】算法，两到三天更新一篇文章，欢迎催更……

专栏内容以分析题目为主，并附带一些对于本题涉及到的数据结构等内容进行回顾与总结，文章结构大致如下，部分内容会有增删：

• Tag：介绍本题牵涉到的知识点、数据结构；
• 题目来源：贴上题目的链接，方便大家查找题目并完成练习；
• 题目解读：复述题目（确保自己真的理解题目意思），并强调一些题目重点信息；
• 解题思路：介绍一些解题思路，每种解题思路包括思路讲解、实现代码以及复杂度分析；
• 知识回忆：针对今天介绍的题目中的重点内容、数据结构进行回顾总结。

Tag

【数学-阶乘】

题目来源

172. 阶乘后的零

题目解读

给你一个整数 n，求出 n! 的结果中尾部 0 的数量，其中：

$$n!=n\ast (n-1)\ast (n-2)\ast ...\ast 3\ast 2\ast 1$$

解题思路

学习 官方题解.

方法一：数学+优化计算

n! 尾零的数量即为 n! 中因子 10 的个数，而 10 = 2 x 5，因此转换成求 n! 中质因子 2 的个数和 质因子 5 的个数的较小值。

由于质因子 5 的个数不会大于质因子 2 的个数（证明如下），我们可以仅考虑质因子 5 的个数 。n! 中质因子 5 的个数等于 [1, n] 的每个数的质因子 5 的个数之和，我们可以遍历 [1, n] 的所有 5 的倍数求出。

代码 1

class Solution {
public:
	int trailingZeroes(int n) {
		int cout_5 = 0;
		for (int i = 5; i <= n; i += 5) {
			int cur = i;
			while (cur % 5 == 0) {
				cout_5++;
				cur /= 5;
			}	
		}
		return cout_5;
	}
};

证明

[1, n] 中 p 的倍数有 $n_1=\lfloor \frac{n}{p}\rfloor$，这些数至少贡献出了 $n_1$ 个质因子 p。一般地，[1, n] 中质因子 p 的个数为

$$\sum _{k=1}^{\infty }\lfloor \frac{n}{p^k}\rfloor$$

上式表明，n 不变，p 越大，质因子的个数越小，因此 [1, n] 中质因子 5 的个数不会大于质因子 2 的个数。证毕。

优化

[1, n] 中质因子 5 的个数为：

$$\sum _{k=1}^{\infty }\lfloor \frac{n}{5^k}\rfloor$$

因此我们可以通过不断将 n 除以 5，并将结果累加即得到答案。

代码 2

class Solution {
public:
    int trailingZeroes(int n) {
        int res = 0;
        while (n) {
            n /= 5;
            res += n;
        }
        return res;
    }
};

复杂度分析

时间复杂度：$O(n)$。优化后的时间复杂度为 $O(logn)$。

空间复杂度：$O(1)$。

写在最后

如果您发现文章有任何错误或者对文章有任何疑问，欢迎私信博主或者在评论区指出 💬💬💬。

如果大家有更优的时间、空间复杂度的方法，欢迎评论区交流。

最后，感谢您的阅读，如果有所收获的话可以给我点一个 👍 哦。