172. 阶乘后的零
172. 阶乘后的零
题目
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 | 转角路径的乘积中最多能有几个尾随零 | 数组 矩阵 前缀和 |