首页 > 代码库 > Leetcode#172 Fractorial Trailing Zero
Leetcode#172 Fractorial Trailing Zero
原题地址
n!含有多少个因子10，则结尾有多少个0
10=2*5，而2的个数肯定比5多，所以n!含有多少个因子5，则结尾有多少个0
如何计算n!有多少个因子5呢？
比如n=13，则：
n! = 13 * 12 * 11 * 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1
| |
含有因子5: 10 5
实际上我们就是在找1到n里面能被5整除的数字有多少个。
显然每隔5个数就有一个带因子5的数字出现，所以就是n/5嘛，错！这样还是少算了一些数，比如25=5*5，丫可是包含2个5的，所以还要加上那些每隔25个数、125个数、...出现的数字（5^i）。
代码：
1 int trailingZeroes(int n) {2 if (n < 0) return -1;3 int res = 0;4 while (n > 0)5 res += (n /= 5);6 return res;7 }
《Cracking the Code》里面也有这道题，这是书上的代码：
1 int trailingZeroes(int n) {2 if (n < 0) return 0;3 int count = 0;4 for (int i = 5; n / i > 0; i *= 5)5 count += n / i;6 return count;7 }
这个代码是无法通过Leetcode测试的，因为i *= 5会溢出，而前面的代码不会。
Leetcode#172 Fractorial Trailing Zero
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。