阶乘后的零

阶乘后的零

地址：

力扣https://leetcode-cn.com/problems/factorial-trailing-zeroes/

题目：

给定一个整数 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 <= 104

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/factorial-trailing-zeroes
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：

之前有计算过 n 的阶乘，如果计算出的结果循环 %10 == 0 ？ 不就可以计算出值了么

这个有点暴力，在 n 特别大的时候这个计算有点夸张，所以不采用

我们知道乘法

2*5 = 10 有一个0

2*5*9 也只有一个0，除非2*5*10才开始有两个0

2*5*10 = 2*5*2*5 这里面有2组匹配： 2 个 2， 2 个 5

题目可以转换为找到多少对 （2，5）

例如：n=16 时，1*2*3*4*5*6*7*8*9*10*11*12*13*14*15*16

2 的因子：2，4，6，8，10，12，14，16

5 的因子：5，10，15

所以有 3 对（2，5），但是

n=25 时，1*2*3*4*5*6*7*8*9*10*11*12*13*14*15*16*18*19*20*21*22*23*24*25

2 的因子：2，4，6，8，10，12，14，16，18，20，22，24

5 的因子：5，10，15，20，25

 2 的因子个数永远比 5 的因子多，所以关注点就变成了查找 5 的因子的个数

那么题目就变成 n/5 

注意特殊数字，25（5*5）的倍数会多一个，125（25*5=5*5*5）多两个

那么在计算的时候这类数字时是不是变成 2*n/25 ，不是啦，n/5 已经计算了一次

那么题目就变成了 n/5+n/25+n/125+...

f(n) = n/5 + f(n/5)

int trailingZeroes(int n){
    if(n <5)
        return 0;

    return n/5 + trailingZeroes(n/5);
}

查看更多刷题笔记