原题
给定一个整数 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
};