跳至主要內容

172. 阶乘后的零


172. 阶乘后的零open in new window

🟠   🔖  数学  🔗 力扣open in new window LeetCodeopen in new window

题目

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,一定是因为两个数中有因子 25,也就是说,问题转化为:n! 最多可以分解出多少个因子 25

最多可以分解出多少个因子 25,主要取决于能分解出几个因子 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 = 525 的倍数,它们每人可以额外再提供一个因子 5

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

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

代码

/**
 * @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 的个数open in new window[✓]递归 数学 动态规划
793阶乘函数后 K 个零open in new window数学 二分查找
2117一个区间内所有数乘积的缩写open in new window数学
2245转角路径的乘积中最多能有几个尾随零open in new window数组 矩阵 前缀和