leetcode 172-阶乘后的零

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

提示 n! = n * (n - 1) * (n - 2) * ... * 3 * 2 * 1

示例 1：

输入：n = 3
输出：0
解释：3! = 6 ，不含尾随 0

示例 2：

输入：n = 5
输出：1
解释：5! = 120 ，有一个尾随 0

示例 3：

输入：n = 0
输出：0
 

提示：

0 <= n <= 10^4
 

进阶：你可以设计并实现对数时间复杂度的算法来解决此问题吗？

思路1：

        只需要判断 n！的结果中因子2的个数和因子5的个数，它们中最小的那个就是 0 的个数

        因为尾数中 0 的个数就是 10 的个数，2 * 5 就是十，也就是说只要找到阶乘结果中 因子  2 的个数和 5 的个数，它们中小的即为最后结果中能有 10 的个数，也就是位数 0 的个数。

int trailingZeroes(int n){
    int num_5 = 0, num_2 = 0, num;
    //不直接求阶乘，因为阶层结果会超出数据的存储范围
    for(int i = n; i > 1; i--){
        num = i;
        while(num % 2 == 0){      //求因子 2 的个数
            num_2 ++;
            num /= 2;
        }
        while(num % 5 == 0){       //求因子 5 的个数
            num_5 ++;
            num /= 5;
        }
    }
    return num_2 < num_5 ? num_2 : num_5;
}

​​​​      思路2: 只求因子 5 的个数

int trailingZeroes(int n){
    int num_5 = 0;
    while(n > 1){       //求因子 5 的个数
        n /= 5;
        num_5 += n;
    
    }
    return num_5;
}