1. lc 172 - 阶乘后的零

  • 题目来源
  • 给定一个整数 n，返回 n! 结果尾数中零的数量。
  • 难度：简单

1.1 解题思路

分析： 首先末尾有多少个 0 ，只需要给当前数乘以一个 10 就可以加一个 0。

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

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

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

总结： 有多少个5就有多少个0。

1.2 复杂度分析

  • 时间复杂度：O(logn)。在这种方法中，我们遍历了5的每个幂直到 n。
  • 空间复杂度：O(1)。

1.3 代码

1
2
3
4
5
6
7
class Solution:
    def trailingZeroes(self, n: int) -> int:
        count = 0
        while n>0: 
            n //= 5
            count += n
        return (count)

参考

[1] windliang. 详细通俗的思路分析. https://leetcode-cn.com/problems/factorial-trailing-zeroes/solution/xiang-xi-tong-su-de-si-lu-fen-xi-by-windliang-3/