面试题 16.05. 阶乘尾数
题目描述
设计一个算法,算出 n 阶乘有多少个尾随零。
示例 1:
输入: 3 输出: 0 解释: 3! = 6, 尾数中没有零。
示例 2:
输入: 5 输出: 1 解释: 5! = 120, 尾数中有 1 个零.
说明: 你算法的时间复杂度应为 O(log n) 。
解法
方法一:数学
题目实际上是求 $[1,n]$ 中有多少个 $5$ 的因数。
我们以 $130$ 为例来分析:
- 第 $1$ 次除以 $5$,得到 $26$,表示存在 $26$ 个包含因数 $5$ 的数;
- 第 $2$ 次除以 $5$,得到 $5$,表示存在 $5$ 个包含因数 $5^2$ 的数;
- 第 $3$ 次除以 $5$,得到 $1$,表示存在 $1$ 个包含因数 $5^3$ 的数;
- 累加得到从 $[1,n]$ 中所有 $5$ 的因数的个数。
时间复杂度 $O(\log n)$,空间复杂度 $O(1)$。
1 2 3 4 5 6 7 |
|
1 2 3 4 5 6 7 8 9 10 |
|
1 2 3 4 5 6 7 8 9 10 11 |
|
1 2 3 4 5 6 7 8 |
|
1 2 3 4 5 6 7 8 |
|
1 2 3 4 5 6 7 8 9 10 11 |
|