LeetCode172—Factorial Trailing Zeroes-蒲公英云

LeetCode172—Factorial Trailing Zeroes

原题

原题链接

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;
    }
};