【前端算法】阶乘后的零，两次遍历

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

示例 1:

输入: 3

输出: 0

解释: 3! = 6, 尾数中没有零。

示例 2:

输入: 5

输出: 1

解释: 5! = 120, 尾数中有 1 个零.

• 说明: 你算法的时间复杂度应为 O(log n) 。

解题代码：

/**
 * @param {number} n
 * @return {number}
 */
var trailingZeroes = function(n) {
    let result = 1;
    let i = 1;
    while (i <= 5) {
        result *= i;
        i++;
    };
    var num = 0;
    while (n > 0) {
        n = (n - (n % 5)) / 5;
        num += n;
    }
    return num
};

知识点

• 求阶乘数字后面的零

末尾0的个数取决于乘法中因子2和5的个数。显然乘法中因子2的个数大于5的个数，所以我们只需统计因子5的个数。

如5！

求5！5/5 = 1；//120 后面一个零

是5的倍数的数有： 1024 / 5 = 204个

是25的倍数的数有：1024 / 25 = 40个

是125的倍数的数有：1024 / 125 = 8个

是625的倍数的数有：1024 / 625 = 1个

所以1024! 中总共有204+40+8+1=253个因子5。

也就是说1024! 末尾有253个0。