172.阶乘后的零

发表于 更新于 分类于 ，

题目

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

示例 1:

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

示例 2:

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

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

思路

这是相当有难度的一道题,要明白这个简单的解法并不简单.

首先先把这个数的阶乘暴力算出来,然后从后往前数多少个零这种做法肯定是不可取的,肯定是有更巧妙的方法的.

先来观察结果的尾数中0的个数与什么有关.

阶乘是指将1到n之间的所有数都乘起来,而在这些数之中,想要得到尾数0,则必然需要2x5才会有0,要么就是2的倍数乘以5或者5的倍数会得到0. 例如:

6!=1x2x3x4x5x6

就是通过2x5来得到尾数0的,所以我们可以得知,尾数0的个数受到2和5的个数限制.

而另一方面,我们通过公式可以得知,2的个数必然是会比5的个数多的,例如上面的式子,可以拆成:

6!=1x2x3x(2x2)x5x(2x3)

所以我们可以进一步得出结论,尾数0的个数受限于5的个数,有多少个5,就总会有多少个2来和它组成一个10来产生一个0.

到了这里我们的目标就从算出尾数有多少个0,变成了给定的阶乘数里面包含了多少个5.例如30!里面能凑出7个5,分别是

5 , 2x5 ,3x5 , 4x5 , 5x5 , 6x5

代码

1
2
3
4
5
6
7
8
9
10
public int TrailingZeroes(int n)
{
    int count = 0;
    while (n > 1)
    {
        count = count + n / 5;
        n = n / 5;
    }
    return count;
}