LeetCode172 Factorial Trailing Zeroes

文章目录
  1. 1. 描述
  2. 2. 样例
  3. 3. 思路
  4. 4. 代码

描述

Given an integer $n$, return the number of trailing zeroes in $n!$.
Note: Your solution should be in logarithmic time complexity.

样例

1
2
3
4
Input:
10
Output:
2

思路

求$n!$末尾零的个数。

不难发现,其末尾的零来源于$n!=1 × 2 × \cdots × n$这一乘法过程中产生了多少个$10$。而$10 = 2 × 5$,因此要统计其中有多少个$2$和多少个$5$,但是由于$2$的数量多于$5$的数量,故只需统计$5$的数量即可。

现在问题转化为:求$n!=1 × 2 × \cdots × n$中有多少个$5$。

显然,能被$5$整除的数至少能贡献$1$个$5$,若同时又能被$5^2$整除,则还可以再贡献一个$5$,若继续能被$5^3$整除,那么还可以再贡献一个$5$… 所以,$ans = \lfloor n / 5\rfloor + \lfloor n / 5^2\rfloor + \lfloor n / 5^3\rfloor + … $

算法时间复杂度:$\mathcal{O}(log_{5}n)$

代码

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
int trailingZeroes(int n) {
int ans = 0;
while (n) {
ans += n / 5;
n /= 5;
}
return ans;
}
};
分享到 评论