LeetCode172—Factorial Trailing Zeroes

逃离我推掉我的手 2022-07-14 01:47 292阅读 0赞

## 原题 ##

[原题链接][Link 1]

> Given an integer n, return the number of trailing zeroes in n!.
> 
> Note: Your solution should be in logarithmic time complexity.
> 
> Credits:  
> Special thanks to @ts for adding this problem and creating all test cases.

## 分析 ##

这个题求n!后面尾随了多少个0？

### **思路1** ###

能产生0的方式，最小公因数分别是2和5，已知n!=n⋅(n−1)⋅(n−2)...2⋅1，这里面至少能提供n2个因数2，因此产生0的重任就在5身上了，关键是看从\[5,n\]这个范围内，能够贡献出多少个因数5。

class Solution {
    public:
        int trailingZeroes(int n) {
            int count = 0;
            for(long i=5;i<=n;i+=5)
            {
                long j = i;
                while(0==j%5)
                {
                    ++count;
                    j/=5;
                }
            }
            return count;
        }
    };

LeetCode提交这个代码，超时。

### **思路2** ###

能不能再简化呢？总之我们是求因数5的个数，那么这5的来源可以是数字5，贡献1个5，数字25贡献两个5，数字30贡献1个5。

对于一个数字n来说，⌊n5⌋ 表示\[1,n\]有多少个能被5整除的数，同理⌊n25⌋表示多少个能被25整除。因此：  
对于求序列中5的因数个数来说，即求\[1,n\]有多少个数能被5整除，能被25整除，能被125整除…  
\[1,n\]中能被5整除的所有数分别贡献1个5，\[1,n\]中所有能被25整除的数分别再贡献1个5…

lass Solution {
    public:
        int trailingZeroes(int n) {
            int count = 0;
            while (n)
            {
                count += n/5;
                n/=5;
            }
            return count;
        }
    };

[Link 1]: https://leetcode.com/problems/factorial-trailing-zeroes/