https://leetcode.com/problems/factorial-trailing-zeroes/
给定一个数N，求其阶乘 (N!) 后面有多少个连续的0
分析：
乘积后面的0只有可能来自于 2 x 5，或者乘数种包括 10，而10也可以分解为 2x5，
因此只需要判断 2，5的数目，而只要出现一个5，就会出现多个偶数，因此2是肯定满足且多余的，因此只需要判断从1到N中有多少个5
class Solution {
public:
int trailingZeroes(int n) {
int num=0;
while(n)
{
num += (n/5);
n/=5;
}
return num;
}
};
结果：
Runtime: 8 ms
Memory Usage: 6 MB
加速方法
速度：移位 > 乘法 > 除法，因此可以将 n/=5 换成 被除数 n 不变，然后把除数每次进行5倍增加。
class Solution {
public:
int trailingZeroes(int n) {
int num=0;
int base=5;
while(n)
{
num += (n/base);
if(base>INT_MAX/5)
break;
else
base*=5;
}
return num;
}
};
结果：
Runtime: 4 ms
Memory Usage: 5.8 MB
------------------------------------------------------------------------------------------
上面的else其实是不需要的，去掉之后可以再次加速
class Solution {
public:
int trailingZeroes(int n) {
int num=0;
int base=5;
while(n)
{
num += (n/base);
if(base>INT_MAX/5)
break;
base*=5; //这里加上else就会加时间
}
return num;
}
};
结果：
Runtime: 0 ms, faster than 100.00% of C++ online submissions for Factorial Trailing Zeroes.
Memory Usage: 5.8 MB, less than 100.00% of C++ online submissions for Factorial Trailing Zeroes.
因此可以看到，同样的算法思想，不同的实现也会带来效率上的不同。