跳转至

LeetCode: 172. 阶乘后的零

1、题目描述

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

示例 1:

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

示例 2:

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

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

2、解题思路

​ 我们知道,如果想要在默认有0,表示是10的倍数,可以看成是5*2的倍数,因此,每一个0,都可以看成是一个因子5,乘以一个偶数的形式

​ 因此,如果想要得到阶乘后面有多少个0,就找出有多少个因子5就可以了

举个例子,假如我们想要求解 n的阶乘后面有多少个0,也就是因子5

当n<5

​ 没有因子5,没有0;

当n>=5

​ 我们将这个很大的数进行因式分解,可以看到 $$ 5*k 5(k-1)...*5 a $$ 其中,a表示不能被5整除的数,

​ k表示最大的那个可以被5整除的数,也就是说已经能够得到k个因子5

​ 然后,我们看到,从1到k又构成了一个阶乘,然后这里面可能也有因子5

​ 同样得到了,k继续往下分

int trailingZeroes(int n) {
    int result = 0;
    while (n >= 5) {
        result += n / 5;
        n /= 5;
    }
    return result;
}