题目:
给定一个整数 n,返回 n! 结果尾数中零的数量。
示例 1:
输入: 3
输出: 0
解释: 3! = 6, 尾数中没有零。
示例 2:
输入: 5
输出: 1
解释: 5! = 120, 尾数中有 1 个零.
说明: 你算法的时间复杂度应为 O(log n) 。
链接:https://leetcode-cn.com/problems/factorial-trailing-zeroes
思路:
1、题目要求统计阶乘后0的个数,而0只和2和5有关。由于阶乘中2的倍数明显大于5,所以这道题主要是计算n的阶乘中5的个数
2、n的阶乘中5的个数 = n/5 + n/(5* 5) + n/(5* 5* 5) ...
Python代码:
class Solution(object):
def trailingZeroes(self, n):
"""
:type n: int
:rtype: int
"""
ret = 0
while n>=5:
ret += n/5
n /= 5
return ret
C++代码:
class Solution {
public:
int trailingZeroes(int n) {
int ret=0;
while(n>=5){
ret += n/5;
n /= 5;
}
return ret;
}
};
网友评论