阶乘末尾0的数量

[编程题]阶乘末尾0的数量

热度指数：11837 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个非负整数 n ，返回 n! 结果的末尾为 0 的数量。

n! 是指自然数 n! 的阶乘,即 : $N!=1 \times 2\times3…(N-2)\times(N-1) \times N$ 。

特殊的, 0 的阶乘是 1 。

数据范围： $0 < n \le 10^{14}$

进阶：空间复杂度 $O(1)$ ，时间复杂度 $O(logn)$

复杂度要求：

不大于 $O(\log n)$

示例1

输入

输出

说明

3!=6

示例2

输入

输出

说明

5!=120

示例3

输入

1000000000

输出

249999998

算法知识视频讲解

Python 3

danspace

class Solution:
    def thenumberof0(self , n: int) -> int:
        # write code here
        count = 0 
        while n > 0:
            count += n//5
            n = n//5
        return count

发表于 2022-04-25 15:57:14 回复(0)

Python 3

mgxjq

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# the number of 0
# @param n long长整型 the number
# @return long长整型
#
class Solution:
def thenumberof0(self , n: int) -> int:
# write code here
result = 0
i = 5
while n >=i:
result += n // i
i *= 5
return result

发表于 2022-01-24 20:26:26 回复(0)

Python 3

冷风tt

分别计算1~n中5的个数，5**2的个数，5**3的个数， ...., 最后结果就是这些个数之和。

class Solution:

def thenumberof0(self , n ):
# write code here
if n < 5:
return 0
res = 0
k = int(math.log(n, 5))
cur = 5
for i in range(k):
res += n // cur
cur *= 5
return res

发表于 2021-07-30 17:19:26 回复(1)

Python 3

HHHChen77

class Solution:
    def thenumberof0(self , n ):
        # 阶乘末尾为0的数量取决于阶乘范围内出现'5'的次数
        # 如 5->1次(5)  25->2次(5*5)  125->3次(5*5*5)
        count = 0
        while n:
            count += (n//5)
            n = n // 5
        # 返回
        return count

发表于 2021-07-27 12:46:50 回复(0)