首页 > 代码库 > [LeetCode] Factorial Trailing Zeroes 阶乘末尾0
[LeetCode] Factorial Trailing Zeroes 阶乘末尾0
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.
Hide Tags
Math 这题应该是2014年年底修改该过测试样本，之前的通过遍历1-n 然后判断每个数5因子的个数，这个简单的遍历方法不行了，时间限制了。
然后既然不能遍历，便只能换个思路，能够构成末尾0，其实决定因素在于1 to n 的数一共有多少个5因子。那么我们这样考虑:
对于5
那么能够被他整除的是 5 10 15 25 30 ...
这样其实便一共有n/5，对于 25 50 这样的数包括了两个5因子，我们在后面会计算的，在考虑5的时候，结果便是 n/5。
对于25
能够被整除的是 25 50 75 ...
这样，其实一共有n/25个，这时候25 中的两个5因子，变都计数了。
对于 125
同样能够被其整除的是125 625...
这样，是不是结果其实便是：
n/5 + n/25 + n/125 ...
这样计算有个问题，会越界，c++ int类型一直乘以5越界时候，会变成 1808548329，题目实验便是使用了这个测试，所以越界的判断需要另外考虑。
代码如下:
#include <iostream>#include <math.h>#include <vector>using namespace std;class Solution {public: int trailingZeroes(int n) { int retCnt=0,tmp5=5; while(tmp5<=n){// cout<<tmp5<<" "<<n<<endl; retCnt+=n/tmp5; tmp5*=5; if(tmp5%5!=0) break; } return retCnt; }};int main(){ Solution sol;// for(int i =1;i<=50;i++){// cout<<"i="<<i<<":"<<sol.trailingZeroes(i)<<endl;// } cout<<sol.trailingZeroes(1808548329)<<endl; cout<<INT_MAX<<endl; return 0;}
[LeetCode] Factorial Trailing Zeroes 阶乘末尾0
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。