题意概述

• 给定一个非负整数n
• 返回n!结果的末尾为0的数量

方法一：数学

思路与具体做法

• 因为0来源于2*5所以一对2和5即可产生一个0，所以0的个数即为阶乘中5的个数和2的个数的最小值
• 又因为2的倍数的数一定比5的倍数的数多，所以只需要统计5的个数了

class Solution {
public:
    long long thenumberof0(long long n) {
        long long ans=0;
		while(n){
			ans+=n/5;
			n/=5;
		} 
		return ans;
    }
};

时间复杂度和空间复杂度分析

• 时间复杂度：$O({}_{5}n)O(\backslash log\_\{5\}\{n\}\; )$,n不断除以5
• 空间复杂度：$O(1)O(1)$，用到常数个额外空间。

方法二：勒让德定理

思路与具体做法

• 定理

• 推广:求$n!n!$中因子$pp$的个数

• 因为$n!=1\ast 2\ast \mathrm{.}\mathrm{.}\ast nn!=1*2*..*n$,所以含有一个$pp$的有 $\frac{n}{p}\backslash frac\{n\}\{p\}$个,含有两个$pp$的有 $\frac{n}{p^2}\backslash frac\{n\}\{p^2\}$个...把以上全部加起来即为答案了

• 求$n!n!$末尾0的个数，即用勒让德定理求$n!n!$中因子10的个数。因子10可拆分2*5。随着a的增加，显然含有2的因子比含有5的因子要多，因此只需要统计包含5因子的个数即可，即p=5，每有一个5，阶乘末尾就会多出来一个0，这样a/5就能统计出第一层5的个数，并依次处理，就能统计出所有5的个数，也就能统计出阶乘末尾0的个数。

class Solution {
public:
    long long thenumberof0(long long n) {
        long long int ans=0;
        long long int p=5;
		while(n>=p){
			ans+=n/p;
			p=p*5;
		} 
		return ans;
    }
};

时间复杂度和空间复杂度分析

• 时间复杂度：$O({}_{5}n)O(\backslash log\_\{5\}\{n\}\; )$,n不断除以5
• 空间复杂度：$O(1)O(1)$，用到常数个额外空间。