172. 阶乘后的零(Python)

题目

难度:★★☆☆☆
类型:数学

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

示例

示例 1:

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

示例 2:

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

解答

我们先来看一下从1到26计算阶乘后的结果:

1!= 1                                      0的个数为: 0
2!= 2                                      0的个数为: 0
3!= 6                                      0的个数为: 0
4!= 24                                     0的个数为: 0
5!= 120                                    0的个数为: 1
6!= 720                                    0的个数为: 1
7!= 5040                                   0的个数为: 1
8!= 40320                                  0的个数为: 1
9!= 362880                                 0的个数为: 1
10!= 3628800                                0的个数为: 2
11!= 39916800                               0的个数为: 2
12!= 479001600                              0的个数为: 2
13!= 6227020800                             0的个数为: 2
14!= 87178291200                            0的个数为: 2
15!= 1307674368000                          0的个数为: 3
16!= 20922789888000                         0的个数为: 3
17!= 355687428096000                        0的个数为: 3
18!= 6402373705728000                       0的个数为: 3
19!= 121645100408832000                     0的个数为: 3
20!= 2432902008176640000                    0的个数为: 4
21!= 51090942171709440000                   0的个数为: 4
22!= 1124000727777607680000                 0的个数为: 4
23!= 25852016738884976640000                0的个数为: 4
24!= 620448401733239439360000               0的个数为: 4
25!= 15511210043330985984000000             0的个数为: 6
26!= 403291461126605635584000000            0的个数为: 6
27!= 10888869450418352160768000000          0的个数为: 6
28!= 304888344611713860501504000000         0的个数为: 6
29!= 8841761993739701954543616000000        0的个数为: 6
30!= 265252859812191058636308480000000      0的个数为: 7

很容易观察到这样的现象:

  1. 从4到5,从9到10,从14到15……阶乘中末尾零的个数增加,说明5对于阶乘结果的影响起决定性作用,每乘以一个含有因子5的数,零的个数增加一;

  2. 从24到25,阶乘中末尾零的个数增加2个,而这一步相当于在24!的基础上乘了25,而25恰好是两个5相乘,实际上可以与两个偶数配对,偶数的个数是要远远多于5的倍数的。

为此,我们可以得出结论:将参与乘法运算的所有数进行因式分解,所有因子中5的个数少于2的个数,阶乘结果末尾零的个数实际上等于因子中5的个数。

我们可以通过以下方式求取因子中5的个数:

class Solution:
    def trailingZeroes(self, n):
        count = 0
        while n > 0:
            count += n // 5
            n /= 5
        return count

写成递归形式是这样:

class Solution:
    def trailingZeroes(self, n):
        if n < 5:
            return 0
        return n // 5 + self.trailingZeroes(n // 5)

如有疑问或建议,欢迎评论区留言~

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • V信:15528063289
    猪_a54c阅读 227评论 0 0
  • 长相思 风儿吹落了花红吹散了梦, 却吹不走相思成空。 雨儿润湿了秀发润湿了泥, 却润不了心字成灰...
    冰雪语阅读 260评论 0 0
  • (1,定位)阴阳,是世界上最早的唯物辩证法。(2,来源)阴阳,是古代人对世界的客观认识。人们看到,事物都是一对一对...
    学而不厌在路上阅读 729评论 2 1
  • 作者:毛志杰(家长课堂) 对于孩子的家庭教育方面,“成绩教育”重要还是“品德教育”重要呢?这的确是个问题。 “郭靖...
    毛哥说教育阅读 1,555评论 2 1
  • 《集装箱改变世界》 创新改变世界,博弈却有可能阻碍创新。不过,世界还是被改变了不是吗? 博弈是什么? 博弈本意是:...
    repo_Bell阅读 306评论 0 0