阶乘后的零

阶乘后的零,第1张

阶乘后的零

地址:

力扣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);
}

查看更多刷题笔记

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/zaji/5702972.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-12-17
下一篇 2022-12-17

发表评论

登录后才能评论

评论列表(0条)

保存