题目

题解

这道题代码不难，关键是数学归纳。
如果把阶乘算出来再求0一定会超时，时间复杂度$O(n)$，pass。
这道题的关键是找2和5的个数，只有2*5才能得到0，而2的个数远多于5，没出现一个5必然有一个2与之结合，那么就转化为找有几个5。
挨个数字找必然会超时，时间复杂度$O(n)$，pass。 那就直接除以5就能找到所有5的个数，然而还没完，
25是两个5，125是三个5，因此n/5的商还要接着循环除以5，直到除不动了。

  • 时间复杂度$O(log_5{n})$
  • 空间复杂度$O(1)$
class Solution {
public:
    int trailingZeroes(int n) {
        int res = 0;
//直接找n中5的个数，第一遍循环是找5，第二遍是找25，然后125，以此类推
        while(n){
            res += n/5;
            n /=5;
        }
        return res;
    }
};

递归一行代码搞定，牛逼

class Solution {
public:
    int trailingZeroes(int n) {
        return n==0? 0 : n/5+trailingZeroes(n/5);
    }
};

参考(https://leetcode-cn.com/problems/factorial-trailing-zeroes/solution/xiang-xi-tong-su-de-si-lu-fen-xi-by-windliang-3/)