标签: 数学
难度: Easy
设计一个算法，算出 n 阶乘有多少个尾随零。
示例 1:
输入: 3 输出: 0 解释: 3! = 6, 尾数中没有零。
示例 2:
输入: 5 输出: 1 解释: 5! = 120, 尾数中有 1 个零.
说明: 你算法的时间复杂度应为 O(log n) 。
Submission
运行时间: 21 ms
内存: 16.1 MB
class Solution:
def trailingZeroes(self, n: int) -> int:
ans=0
while n!=0:
ans+=n//5
n//=5
return ans
Explain
题解的思路是计算阶乘中尾随零的数量。尾随零是由因子10产生的，而10可以分解为2和5。在阶乘数中，因子2的数量总是多于因子5的数量，因此尾随零的数量由因子5的数量决定。题解通过循环减少n的值，每次将n除以5，并累加结果到ans中。这样可以计算出包含在n!中的所有5的因子的总数，从而得到尾随零的数量。
时间复杂度: O(log n)
空间复杂度: O(1)
class Solution:
def trailingZeroes(self, n: int) -> int:
ans = 0 # 用于累计尾随零的数量
while n != 0:
ans += n // 5 # 计算n中包含的5的因子数量
n //= 5 # 更新n值为原来的1/5
return ans # 返回尾随零的总数
Explore
在计算阶乘数的尾随零时，每个零都来源于因子10，而10可分解为2和5。在任何阶乘数中，因子2的出现频率总是高于因子5，因为每隔一个数就有一个偶数，从而提供了一个因子2。这意味着因子2不会成为限制尾随零数量的因素。相对而言，因子5较少，因此决定了尾随零的数量。只要统计因子5的数量，就可以确定阶乘结果尾随零的数量。
这个算法通过不断地将n除以5并累加结果的方式，能够有效地计算出阶乘数中所有的5的因子。初始的除以5是为了找出n以内直接被5整除的数字（每一个都贡献一个5作为因子）。然后，再除以5是为了找出被25整除的数字（每一个都贡献额外的一个5因为25=5x5），依此类推。这样可以确保所有5的幂的贡献都被计入，从而准确地统计出所有可能的含5的因子。
这种方法在处理非常大的n时依然有效且效率较高。算法的时间复杂度主要取决于对n连续除以5的次数，这是一个对数级别的操作（基于5的对数）。例如对于n=10^9，最多需要进行大约log5(10^9)约等于13次的迭代，这在计算上是非常快速的。因此，对于非常大的数，这个算法仍然可以在非常短的时间内得出结果，没有明显的性能瓶颈。