阶乘尾数
难度:
标签:
题目描述
Write an algorithm which computes the number of trailing zeros in n factorial.
Example 1:
Input: 3 Output: 0 Explanation: 3! = 6, no trailing zero.
Example 2:
Input: 5 Output: 1 Explanation: 5! = 120, one trailing zero.
Note: Your solution should be in logarithmic time complexity.
代码结果
运行时间: 21 ms, 内存: 16.1 MB
/*
题目思路：
使用 Java Stream 的方法实现相同的逻辑。
主要是通过流的方式计算从 5 到 n 的每一个 5 的倍数的数量。
*/
import java.util.stream.Stream;
public class Solution {
public int trailingZeroes(int n) {
return Stream.iterate(5, i -> i <= n, i -> i * 5)
.mapToInt(i -> n / i) // 计算每个 5 的倍数因子数量
.sum(); // 汇总所有的因子数量
}
}解释
方法:
题解的思路是计算阶乘中尾随零的数量。尾随零是由因子10产生的，而10可以分解为2和5。在阶乘数中，因子2的数量总是多于因子5的数量，因此尾随零的数量由因子5的数量决定。题解通过循环减少n的值，每次将n除以5，并累加结果到ans中。这样可以计算出包含在n!中的所有5的因子的总数，从而得到尾随零的数量。
时间复杂度:
O(log n)
空间复杂度:
O(1)
代码细节讲解
🦆
为什么在计算阶乘尾数中零的数量时，只需要关注因子5的数量而不是因子2的数量？
▷🦆
在算法中，每次将n除以5并累加的过程是如何确保计算了所有可能的包含5的因子的情况？
▷🦆
在实际应用中，这种方法处理非常大的n（例如10^9级别）时是否依然有效？有没有可能的性能瓶颈？
▷