Factorial Trailing Zeroes 172

题目描述：

给出一个integer n，计算n！结尾0的个数

---

题目分析：

考虑暴力，计算n！统计最后面0的个数。先不说数字溢出，其次n是一个integer ，O(n)复杂度超时

 

我们接着考虑，产生0的情况

只有包含因子5的数乘以一个偶数会在结尾产生0（5*2,15*2,75*2），因为偶数的个数大于因子包含5的数的个数，那么我们只要考虑包含因子5的数；

 

但是是不是包含因子5的数一定只会在结尾产生一个0呢，对于25*4提供两个0，这是因为25，包含两个因子5（5*5）；同样125会提供3个0；

 

这样只要考虑1-n之间有多少包含因子5的数，有多少个包含因子25的数，有道少个包含因子125的数。。。。以此累加

 

---

代码:

1 int trailingZeroes(int n) { 2 int mod=5; 3 int cnt=0; 4 while(n/mod){ 5 cnt+=n/mod; 6 mod*=5; 7 } 8 return cnt; 9 }

 

转载于:https://www.cnblogs.com/li-xingtao/p/4215246.html

总结

以上是生活随笔为你收集整理的Factorial Trailing Zeroes 172的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。