Fork me on GitHub

LeetCode-13.数学

十三、数学

172. 阶乘后的零

链接:https://leetcode-cn.com/problems/factorial-trailing-zeroes/

给定一个整数 n,返回 n! 结果尾数中零的数量。

示例 1:

输入: 3
输出: 0
解释: 3! = 6, 尾数中没有零。
示例 2:

输入: 5
输出: 1
解释: 5! = 120, 尾数中有 1 个零.
说明: 你算法的时间复杂度应为 O(log n) 。

题解一:

如果依靠算出阶乘结果,再计算有多少个0,很容易溢出。

思路:末尾有多少个0,只需要给当前数乘以一个10,就可以加一个0.

比如5!,也就是 5 4 3 2 1 = 120,我们发现结果会有一个 0,原因就是 2 和 5 相乘构成了一个 10。而对于 10 的话,其实也只有 2 * 5 可以构成,所以我们只需要找有多少对 2/5。

11! = 11 10 9 8 7 6 5 4 3 2 1 = 11 (2 5) 9 (4 2) 7 (3 2) (1 5) (2 2) 3 (1 2) 1

对于含有 2 的因子的话是 1 2, 2 2, 3 2, 4 2 …

对于含有 5 的因子的话是 1 5, 2 5…

含有 2 的因子每两个出现一次,含有 5 的因子每 5 个出现一次,所有 2 出现的个数远远多于 5,换言之找到一个 5,一定能找到一个 2 与之配对。所以我们只需要找有多少个 5。

直接的,我们只需要判断每个累乘的数有多少个 5 的因子即可。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
def trailingZeroes(self, n: int) -> int:
count=0
for i in range(n+1):
tmp=i
while tmp>0:
if tmp%5==0:
count+=1
tmp//=5
else:
break
return count

以上算法超时,继续优化。

对于一个数的阶乘,5 的因子一定是每隔 5 个数出现一次,也就是下边的样子。

n! = 1 * 2 * 3 * 4 * (1 * 5) * ... * (2 * 5) * ... * (3 * 5) *... * n

因为每隔 5 个数出现一个 5,所以计算出现了多少个 5,我们只需要用 n/5 就可以算出来。

但还没有结束,继续分析。

... * (1 * 5) * ... * (1 * 5 * 5) * ... * (2 * 5 * 5) * ... * (3 * 5 * 5) * ... * n

每隔 25 个数字,出现的是两个 5,所以除了每隔 5 个数算作一个 5,每隔 25 个数,还需要多算一个 5。

也就是我们需要再加上 n / 25 个 5。

同理我们还会发现每隔 5 5 5 = 125 个数字,会出现 3 个 5,所以我们还需要再加上 n / 125 。

综上,规律就是每隔 5 个数,出现一个 5,每隔 25 个数,出现 2 个 5,每隔 125 个数,出现 3 个 5,以此类推。

最终 5 的个数就是 n / 5 + n / 25 + n / 125 …

写程序的话,如果直接按照上边的式子计算,分母可能会造成溢出。所以算 n / 25 的时候,我们先把 n 更新,n = n / 5,然后再计算 n / 5 即可,后边的同理。

1
2
3
4
5
6
7
class Solution:
def trailingZeroes(self, n: int) -> int:
count=0
while n>0:
count+=n//5
n//=5
return count
支持,让我的文章更加优秀!