阶乘后的零
Leetcode 172. 阶乘后的零
题意
给定一个整数n， 返回n！结果尾数中零的数量。
示例一
输入: 3
输出: 0
解释: 3! = 6, 尾数中没有零。
示例二
输入: 5
输出: 1
解释: 5! = 120, 尾数中有 1 个零.
说明
你算法的时间复杂度应为O（log n）。
分析：
- 通过对阶乘组成的数进行质数分解，可得阶乘出现尾数为零的结果，只能由5*2所构成，而2的个数远多于5的个数，因此只需计算质数分解后5出现的个数即可。
- 假设n=25，那么由质数分解后，出现5的数总共有5， 10， 15， 20， 25，尾数出现零的个数为6个;
- 其中25为
,因此，n=25的可以简单记为n分别除以
,
,...,
，结果的和。
综上，代码为：
class Solution {
public:
int trailingZeroes(int n) {
// 判断n是否为零，若为零则返回零，否则返回质数分解中5出现的个数。
return n == 0 ? 0 : n/5 + trailingZeroes(n/5);
}
};
网友评论