Leetcode: Factorial Trailing Zeroes
Leetcode: Factorial Trailing Zeroes
卡尔曼和玻尔兹曼谁曼
发布于 2019-01-25 14:43:45
发布于 2019-01-25 14:43:45
题目： Given an integer n, return the number of trailing zeroes in n!.
Note: Your solution should be in logarithmic time complexity.
即要求计算n的阶乘结果中后面0的个数。
分析： 对n!做质因数分解有：n!=2x*3y*5z*… 显然0的个数等于min(x,z)，并且min(x,z)==z。 所以我们需要求n!中分解因式后5的个数。[n/k]代表1~n中能被k整除的个数，即我们需要求出n/5+(n-1)/5+(n-2)/5+…+1/5的个数。
下面使用C++语言进行示例：
所以，方法一：
class Solution {
public:
int trailingZeroes(int n)
{
int count = 0;
int current;
for (int i = 1; i <= n; i++)
{
current = i;
while(current % 5 == 0)
{
count++;
current /= 5;
}
}
return count;
}
};但是，上面的示例中起作用的只有被5整除的那些数。能不能只对这些数进行计数呢？所以有方法二：
class Solution {
public:
int trailingZeroes(int n)
{
int count = 0;
while(n)
{
count += n/5;
n /= 5;
}
return count;
}
};本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2015年03月04日，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读