172. 阶乘后的零

🟠   🔖  数学  🔗 LeetCode

题目

Given an integer n, return the number of trailing zeroes inn!.

Note that n! = n * (n - 1) * (n - 2) * ... * 3 * 2 * 1.

Example 1:

Input: n = 3

Output: 0

Explanation: 3! = 6, no trailing zero.

Example 2:

Input: n = 5

Output: 1

Explanation: 5! = 120, one trailing zero.

Example 3:

Input: n = 0

Output: 0

Constraints:

• 0 <= n <= 10^4

Follow up: Could you write a solution that works in logarithmic time complexity?

题目大意

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

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

解题思路

两个数相乘结果末尾有 0，一定是因为两个数中有因子 2 和 5，也就是说，问题转化为：n! 最多可以分解出多少个因子 2 和 5？

最多可以分解出多少个因子 2 和 5，主要取决于能分解出几个因子 5，因为每个偶数都能分解出因子 2，因子 2 肯定比因子 5 多得多。

那么，问题转化为：n! 最多可以分解出多少个因子 5？

难点在于像 25，50，125 这样的数，可以提供不止一个因子 5，不能漏数了。

• 我们假设 n = 125，来算一算 125! 的结果末尾有几个 0：

• 首先，125 / 5 = 25，这一步就是计算有多少个像 5，15，20，25 这些 5 的倍数，它们一定可以提供一个因子 5。

• 但是，像 25，50，75 这些 25 的倍数，可以提供两个因子 5，那么我们再计算出 125! 中有 125 / 25 = 5 个 25 的倍数，它们每人可以额外再提供一个因子 5。

• 接着，125 = 5 x 5 x 5，像 125，250 这些 125 的倍数，可以提供 3 个因子 5，那么我们还得再计算出 125! 中有 125 / 125 = 1 个 125 的倍数，它还可以额外再提供一个因子 5。

• 所以 125! 最多可以分解出 25 + 5 + 1 = 31 个因子 5，也就是说阶乘结果的末尾有 31 个 0。

代码

/**
 * @param {number} n
 * @return {number}
 */
var trailingZeroes = function (n) {
	let res = 0,
		divisor = 5;
	while (divisor <= n) {
		res += (n / divisor) | 0;
		divisor *= 5;
	}
	return res;
};

相关题目

题号	标题	题解	标签	难度
233	数字 1 的个数		递归 数学 动态规划
793	阶乘函数后 K 个零		数学 二分查找
2117	一个区间内所有数乘积的缩写		数学
2245	转角路径的乘积中最多能有几个尾随零		数组 矩阵 前缀和