每日一题-阶乘后的零

发表于 更新于 分类于 Waline：

172. 阶乘后的零

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/factorial-trailing-zeroes

题目

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

提示 n! = n * (n - 1) * (n - 2) * ... * 3 * 2 * 1

思路

最暴力的方法就是直接求出阶乘然后求该结果末尾有多少个0，但是阶乘增长速度极快，题目中n规模为1e4显然不可行。简单分析可知答案中的0来自因子5的个数，直接求阶乘中5个数即可，该方法复杂度为O(nlogn)。进一步分析数字5每隔5个数就出现一次：1,5,15,...，同时每隔25个数多一个5：25=5*5,50=5*5*2,...，以此类推每隔125个数又多一个5。因此可直接计算5个数为

$$k_5=\frac{n}{5}+\frac{n}{25}+\cdots \frac{n}{5^x}=\frac{n}{5}+\frac{n/5}{5}+\cdots \frac{n/5^{x-1}}{5}$$

代码1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
	public:
	    int trailingZeroes(int n) {
		int ans = 0;
		for (int i = 5 ; i <= n ; ++i) {
			int k = i;
			while(k >= 5 && k%5 == 0) {
				++ans;
				k /= 5;
			}
		}
		return ans;
	}
}
;

代码2

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
	public:
	    int trailingZeroes(int n) {
		int ans = 0;
		while(n) {
			ans += n/5;
			n /= 5;
		}
		return ans;
	}
}
;