[LeetCode] Factorial Trailing Zeroe

时间：2015-04-11 16:21:24 阅读：124 评论：0 收藏：0 [点我收藏+]

Factorial Trailing Zeroes

Given an integer n, return the number of trailing zeroes in n!.

Note: Your solution should be in logarithmic time complexity.
解题思路：

n!=2^x3^y5^z...，注意到一个2和一个5贡献一个末尾的0，因此只需计算min(x,z)即可。又因为n/2和n/5分别表示n!中的因子能被2和5整除的个数，n/2>=n/5，因此min(x, z)=z。我们只需要计算z即可。

如何计算z呢？n/5表示n!中被5整数的个数（贡献至少一个0）， n/(5^2)表示被25整除的个数（贡献至少2个0）...，因此z的计算代码如下：

class Solution {
public:
    int trailingZeroes(int n) {
        int ret = 0;
        while(n)
        {
            ret += n /= 5;
        }
        return ret;
    }
};

扩展思维：

曾经做过，30!的三进制表示中，末尾0的个数有多少个？注意到在三进制中，每逢三便给结果贡献一个0，因此0的个数为30/3+30/9+30/27=14。注意这里的除法是整数除法。

[LeetCode] Factorial Trailing Zeroe

原文：http://blog.csdn.net/kangrydotnet/article/details/44995811

踩

(0)

评论一句话评论（0）

分享档案

更多>

2021年09月23日 (328)
2021年09月24日 (313)
2021年09月17日 (191)
2021年09月15日 (369)
2021年09月16日 (411)
2021年09月13日 (439)
2021年09月11日 (398)
2021年09月12日 (393)
2021年09月10日 (160)
2021年09月08日 (222)

[LeetCode] Factorial Trailing Zeroe

Factorial Trailing Zeroes Given an integer n, return the number of trailing zeroes in n!. Note: Your solution should be in logarithmic time complexity. 解题思路：

n!=2^x*3^y*5^z...，注意到一个2和一个5贡献一个末尾的0，因此只需计算min(x,z)即可。又因为n/2和n/5分别表示n!中的因子能被2和5整除的个数，n/2>=n/5，因此min(x, z)=z。我们只需要计算z即可。

Factorial Trailing Zeroes

Given an integer n, return the number of trailing zeroes in n!.

Note: Your solution should be in logarithmic time complexity.
解题思路：

n!=2^x3^y5^z...，注意到一个2和一个5贡献一个末尾的0，因此只需计算min(x,z)即可。又因为n/2和n/5分别表示n!中的因子能被2和5整除的个数，n/2>=n/5，因此min(x, z)=z。我们只需要计算z即可。