题目描述

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

样例

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

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

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

算法分析

• 1、假设 $n! = k$，k尾后又多少个0，取决于k能分解出多少个10，由于10 = 2 * 5，因此k尾后有多个10，取决于k有能分解出多少个2 和 5,
• 2、假设 $n! = k = 2^a \times 5^b \times .... $，则求k尾后有多少个10，等价于求Min(a, b);
• 3、如何求2的次数a和5的次数b的值，P = 2 和P = 5，枚举质因子P，n!表示1 * 2 * 3... * n,从1到n中，求P的次数：$\lfloor \frac{n}{p} \rfloor + \lfloor \frac{n}{p^2} \rfloor + \lfloor \frac{n}{p^3} \rfloor …$(一共有$log_{p}n$项)
  • P的倍数有$\lfloor \frac{n}{p} \rfloor$个
  • P^2的倍数有$\lfloor \frac{n}{p^2} \rfloor$个
  • P^3的倍数有$\lfloor \frac{n}{p^3} \rfloor$个
  • …
• 4、又由于$\lfloor \frac{n}{2} \rfloor + \lfloor \frac{n}{2^2} \rfloor + \lfloor \frac{n}{2^3} \rfloor … > \lfloor \frac{n}{5} \rfloor + \lfloor \frac{n}{5^2} \rfloor + \lfloor \frac{n}{5^3} \rfloor …$，因此只需要求出5的次数即可，即是阶乘尾后0的个数

时间复杂度 $O(log_{5}n)$

Java 代码

class Solution {
    public int trailingZeroes(int n) {
        int res = 0;
        while(n != 0)
        {
            res += n / 5;
            n /= 5;
        }
        return res;
    }
}