原题
给定一个整数 n,返回 n! 结果尾数中零的数量。
示例 1:
输入: 3
输出: 0
解释: 3! = 6, 尾数中没有零。
示例 2:
输入: 5
输出: 1
解释: 5! = 120, 尾数中有 1 个零.
说明: 你算法的时间复杂度应为 O(log n) 。
解 :
找阶乘后的零,很简单的,我们发现,当 n 为 5 的因数时,就会有5*2 、10*1
,阶乘后末尾就会有零,所以我们列出一些情况。
n | 零的个数 |
---|---|
5 | 1 |
10 | 2 |
15 | 3 |
20 | 4 |
25 | 6 |
30 | 7 |
35 | 8 |
40 | 9 |
45 | 10 |
50 | 12 |
我们发现,当 n 为5 的倍数时,逐渐增长,但当 n 为25 ,50 时出现了意外,稍加思索就会发现,当 n 为 25 的倍数时,阶乘时会有 25*4
出现两个零
var trailingZeroes = function (n) {
let sum = 0
while (n >= 5) {
n = Math.floor(n / 5)//只要还为5的倍数,就继续相加
sum += n
}
return sum
};