标签: 数学
难度: Medium
给定一个整数 n ，返回 n! 结果中尾随零的数量。
提示 n! = n * (n - 1) * (n - 2) * ... * 3 * 2 * 1
示例 1：
输入：n = 3 输出：0 解释：3! = 6 ，不含尾随 0
示例 2：
输入：n = 5 输出：1 解释：5! = 120 ，有一个尾随 0
示例 3：
输入：n = 0 输出：0
提示：
0 <= n <= 104
进阶：你可以设计并实现对数时间复杂度的算法来解决此问题吗？
Submission
运行时间: 20 ms
内存: 16.1 MB
class Solution:
def trailingZeroes(self, n: int) -> int:
ans = 0
while n:
n //= 5
ans += n
return ans
Explain
该题解利用了数学分析的方法来计算阶乘结果中尾随零的数量。观察可知，只有当出现 2 和 5 相乘时才会产生尾随零。而 2 的数量远大于 5 的数量，因此 5 的个数决定了尾随零的数量。通过计算 n 中包含的 5 的因子数，即可得到尾随零的数量。具体做法是通过循环不断地将 n 除以 5，并累加商，直到 n 为 0 为止。
时间复杂度: O(log n)
空间复杂度: O(1)
class Solution:
def trailingZeroes(self, n: int) -> int:
ans = 0
while n:
n //= 5 # 将 n 除以 5
ans += n # 累加 n 除以 5 的商
return ans # 返回尾随零的数量
Explore
在计算阶乘的结果中尾随零的数量时，我们需要考虑因子2和因子5的配对。每对包含一个2和一个5的因子可以产生一个零。在大多数情况下，因子2的数量会超过因子5的数量，因为很多偶数都包含因子2，而只有每隔几个数字才有因子5（如5, 10, 15, 20等）。因此，在阶乘中，限制尾随零数量的通常是因子5的个数，因为它们比因子2更稀少。
通过不断将n除以5并累加结果的方法，可以有效计算出n的阶乘中包含的因子5的总数。首次将n除以5可以计算出小于或等于n的数字中能被5整除的数量。随后，再将得到的商继续除以5，可以计算出能被25整除的数字的数量，因为这些数字中每个至少包含两个因子5。这个过程重复进行，直到商为0，可以确保计算出所有因子5的数量，包括那些因为高次幂而多次计算的情况。
使用这种方法计算尾随零的数量是准确的，不会导致计算过或计算少。这是因为算法考虑了所有可以被5整除的数，以及能被更高次幂的5整除的数（例如25, 125等）。每次除以5实际上是在考虑不同层次的因子5，这确保了即使在包含多个5因子的情况下也不会遗漏。因此，这种方法可以准确地计算出尾随零的数量，无论n的值有多大。