【刷题笔记】阶乘尾数

设计一个算法，算出 n 阶乘有多少个尾随零。

示例 1:

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

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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/factorial-zeros-lcci

         注意，要我们求阶乘的尾随零。

        我一开始的解法是先计算出阶乘，然后利用递归的算法逐步统计尾数是否为0然后累加。可是当数字到了20以上之后，就需要用更大的数进行储存，并且也要进行递归，会耗内存，效率也不高。所以通过分析题目和题解，自己终于了解了利用质因子的解法。

        比如一个数20，算此数的阶乘。

        1 * 2 * 3 * ... * 5 *... * 10 *... 15 * ... * 20 = 20!

        首先明确要求尾随数的个数。那么这个0是如何诞生的呢？无非是10罢。10 = 2 * 5。那么我们只需找 2 * 5这一对的个数就好了。2的出现5不一定会出现（1 * 2 * 3 * 4）4！，但是5的出现2就会出现了。所以我们就可以将问题转化为找5的个数。

        那么，20/5 = 4 ---> 4 * 5就表现了最后一个数就是20，看上面的20阶乘的式子，标红的地方就可以这么写下来：1*5 2*5 3*5 4*5 所以就有4个5，这样尾巴就会出现5个零。

        在举一个，比如40! = 1*2*...*5*...*10*...15*...*20*...*25*...*30*...35*...*40。我们会发现这一列会有40/5=8，但是这个8中（1,2,3,4,5,6,7,8）也存在一个5，即5*5。所以5的个数便就是40/5=8,8/5=1。所以5的个数便就是9。

        上述例子也就说明了找5的个数便即可就将这个要阶乘的最后一个数循环除5，除到为0为止，统计每次5的倍数，然后相加即可。

代码如下：

int trailingZeroes(int n) {
    //统计该数有多少个5
    int sum = 0;
    while(n)
    {
        n /= 5;
        sum += n;
    }
    return sum;
}