关于[LeetCode]Factorial Trailing Zeroes O(logn)解法的理解

时间：2023-01-07 06:01:35

题目描述：

Given an integer n, return the number of trailing zeroes in n!.

题目大意：

给定一个整数n，返回n!（n的阶乘）结果中后缀0的个数（如5!=120，则后缀中0的个数为1）。

解题思路：

 int trailingZeroes(int n) {

    return (n/>)?trailingZeroes(n/)+n/:;

 }

首先这是LeetCode中时间复杂度为O(logn)的解法。

可以简单的知道，阶乘结果中后缀0的个数取决于n!中因数5的个数，因为5x2等于10，这样就出现了0，而因数中2的个数总是比5的个数多的，如5！=1x2x3x4x5，其中5x2得一个0,因数5的个数只有1个，因数2的个数由3个（2,4=2x2）。

重点是为什么上述代码可以求出阶乘中因数5的个数？

让我们举个阶乘61!的例子，一开始61/5=12，这说明1到61中有12个数可以被5整除（即具有因数5），分别是

5

而其他数相乘不会产生0，所以不用再考虑其他数了。

可以看出这12个数中都包含了因数5，但并不是每个数中都只包含1个因数5，如25=5x5，它包含两个因数5。所以，为了计算所有的因数5的个数，我们可以把这12个数做些改变，如

5 =5x1         =5x2

=5x3         =5x4

=5x5         =5x6

=5x7         =5x8

=5x9         =5x10

=5x11        =5x12

可以看出，我们从12个数中找到了12个因数5，剩下了1到12的序列。1到12的序列中也是有因数5的，那么1到12的序列中因数5的个数不就相当于找12!阶乘结果因数5的个数（即阶乘结果中后缀0的个数），这时候就重复递归，即代码中的trailingZeroes(n/5);

当n/5小于0，n小于5，自然就没有因数5了。

以上就是对LeetCode中时间复杂度为O(logn)的解法的理解，本文为本作者原创，转载请注明出处！

相关文章