【数学】leetcode 阶乘后的零

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

示例 1:

输入: 3
输出: 0
解释: 3! = 6, 尾数中没有零。
示例 2:

输入: 5
输出: 1
解释: 5! = 120, 尾数中有 1 个零.
说明: 你算法的时间复杂度应为 O(log n) 。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/factorial-trailing-zeroes

AC代码

class Solution {
    /**
     * 思路
     * 任意两个数相乘，都可以转化为质数相乘的形式，比如4*6=(2^3)*3，n!也一样可以转化为质数相乘的形式
     * 质数中，只有2*5会产生0，而2的数量一定比5多（每5个数有两个2，一个5），所以本题的结果，其实就是n!中含因子5的数量
     * 设最终结果为result
     * 假设1到n中，共有k1个5^1的倍数，5^1至少含1个因子5，result += k1
     * 假设1到n中，共有k2个5^2的倍数，5^2至少含2个因子5，但是其中1个上一步已经算过了，所以新增的因子5的数量只有k2，result += k2
     * 假设1到n中，共有k3个5^3的倍数，5^3至少含3个因子5，但是其中2个上一步已经算过了，所以新增的因子5的数量只有k3，result += k3
     * 依此类推
     * @param n
     * @return
     */
    public int trailingZeroes(int n) {
        int result = 0;
        // multiple是5的倍数
        for (long multiple = 5; multiple <= n; multiple *= 5) {
            result += n / multiple;
        }
        return result;
    }
}

image.png