P4777.阶乘末尾0（非hot100）
在线刷题
本题来源于26年3月底华为实习AI方向手撕真题，同学写的面经在这
原题来自LeetCode 172. 阶乘后的零
题目内容
给定一个数n，n 的阶乘末尾有多少数字 ′0′ ?
输入描述
一个正整数 n 。
1≤n≤105
输出描述
n 的阶乘包含 ’0′ 的数量。
**样例1 **
输入
7
输出
1
说明
7 的阶乘是 5040 ，其中有 1 个数字 ′0′
思路
1.直接算阶乘，不现实：因为n 很大，数据量大了之后就超出计算机能够存储的整数范围了。
2.大数模拟呢？也不现实：
因为每次n∗(n+1) ,数位几乎是成线性增长的。当n=105 时，n!的数位长度是4∗105 。
考虑每一次乘法的复杂度是Ω(n)的，一共要做n次乘法计算，复杂度是Ω(n2)的。1010次运算，计算机大概要跑200秒左右。显然不符合要求。
3.正确解法：想清楚阶乘中末尾的0是怎么来的
一个数末尾为什么会有0 ？ 因为它的因子里有10 。
而10=2×5
所以问题本质上就变成了：
在 n! 的质因子分解里，一共能凑出多少对 2×5。
**例如7的阶乘后面为什么有1个0？因为它质因分解后能凑出一对2×5**👇
根据下图结果不难发现，阶乘里的因子2 的个数永远比 因子5 多👇
[1,n] 中含有因子2的数，也就是偶数，有2n 个
[1,n] 中含有因子5的数，也就是5的倍数的数，有5n 个。 明显是少于偶数的个数的。
所以问题变成了:n!里有多少个因子5 。
从数轴上来看，就是统计方块5的个数👇
那么我们可以循环[1,n]中的每个数，不停的从这个数里除掉5 ， 直到没有因子5为止
def count_fives_in_factorial (n):
ans_5 = 0
# 枚举每一个数
for i in range(1 , n + 1):
# 统计这个数里有多少个因子5
x = i
while x % 5 == 0:
x //= 5
ans_5 += 1
return ans_5
n = int(input())
print(count_fives_in_factorial(n))
#include <iostream>
using namespace std;
int count_fives_in_factorial(int n) {
int ans_5 = 0;
// 枚举每一个数
for (int i = 1; i <= n; i++) {
// 统计这个数里有多少个因子5
int x = i;
while (x % 5 == 0) {
x /= 5;
ans_5 += 1;
}
}
return ans_5;
}
int main() {
int n;
cin >> n;
cout << count_fives_in_factorial(n) << endl;
return 0;
}
import java.util.Scanner;
public class Main {
public static int count_fives_in_factorial(int n) {
int ans_5 = 0;
// 枚举每一个数
for (int i = 1; i <= n; i++) {
// 统计这个数里有多少个因子5
int x = i;
while (x % 5 == 0) {
x /= 5;
ans_5 += 1;
}
}
return ans_5;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
System.out.println(count_fives_in_factorial(n));
}
}
优化：逐行计算
相对于[1,n] , 含有因子5的数是稀疏的，也就是上述循环中很多<不是5的倍数的数>是完全没必要去统计的👇
所以比起统计所有正整数，更直接的办法是：
有多少个数能提供 1 个 5
有多少个数能提供 2 个 5
有多少个数能提供 3 个 5
...
而一个个去找含有因子5的数复杂度过高，我们考虑逐行计算！
先考虑第一行的5的个数，它本质上就是在计算：有多少个数至少包含一个因子5 ， 这个个数显然是5n
再考虑第二行的5的个数，它本质上就是在计算：有多少个数至少包含两个5 ， 这个个数显然是52n=25n
所以逐行计算我们的答案就是:5n+25n+125n+... ， 一直到分式为零为止
代码实现如下👇
from typing import List
class Solution:
def trailingZeroes(self, n: int) -> int:
# 统计阶乘末尾 0 的个数，本质是统计因子 5 的个数
ans_5 = 0
i = 5
# 依次统计 5、25、125... 的倍数个数
while i <= n:
ans_5 += n // i
i *= 5
return ans_5
n = int(input())
print(Solution().trailingZeroes(n))
#include <iostream>
using namespace std;
class Solution {
public:
int trailingZeroes(int n) {
// 统计阶乘末尾 0 的个数，本质是统计因子 5 的个数
int ans_5 = 0;
int i = 5;
// 依次统计 5、25、125... 的倍数个数
while (i <= n) {
ans_5 += n / i;
i *= 5;
}
return ans_5;
}
};
int main() {
int n;
cin >> n;
cout << Solution().trailingZeroes(n) << endl;
return 0;
}
import java.util.Scanner;
class Solution {
public int trailingZeroes(int n) {
// 统计阶乘末尾 0 的个数，本质是统计因子 5 的个数
int ans_5 = 0;
int i = 5;
// 依次统计 5、25、125... 的倍数个数
while (i <= n) {
ans_5 += n / i;
i *= 5;
}
return ans_5;
}
}
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
System.out.println(new Solution().trailingZeroes(n));
}
}
面试问答
1.本题的算法思路是什么？(朴素做法)
一道经典的数学题。阶乘末尾零的个数取决有多少个因子10 , 而因子10由质因子对2,5 所决定。又由于5的因子个数一定少于2的。所以考虑直接计算阶乘中因子5的个数。循环枚举[1,n] , 每次不断用5除尽这个数， 从而得到每个数中因子5的个数，最后输出答案即可。
时间复杂度：外层循环n次，内层循环并不是每次都会触发，它本质在计算[1,n]范围内因子5的总个数，总共计算5n+25n+125n+...<log5n 次。总的循环次数不超过log5n , 则复杂度为O(log5n)
一般面试中大概率不要用最优解法，可以先实现朴素解法。如果面试官要求进一步优化，可以再考虑写最优解。
