阶乘后的零 🌟🌟🌟中等
课后作业
问题描述
原文链接：172. 阶乘后的零
问题描述
给定一个整数 n ，返回 n! 结果中尾随零的数量。
提示 n! = n * (n - 1) * (n - 2) * ... * 3 * 2 * 1
示例 1：
输入：n = 3
输出：0
解释：3! = 6 ，不含尾随 0
示例 2：
输入：n = 5
输出：1
解释：5! = 120 ，有一个尾随 0
示例 3：
输入：n = 0
输出：0
提示：
0 <= n <= 104
代码实现
Java
class Solution {
/*思路
1.一个数乘以 10 就会产生一个0，只需要找哪些数相乘可以得到 10 就可以了。
2. 哪些数相乘可以得到 10=》 2 * 5。 5*4=20=10*2
3、问题转化为：n!可以分解成多少对 2 * 5.=》
注意：1 2 3 4 ...n，2的个数一定比 5 多。 4 = 2 * 2
4、问题继续转化：n!一个有多少数可以被5整除。 25/5=5 5/5 = 1=》25算两个5
//优化
1.....20=>4
1.....25=>6
1....50=>12
sum = n/5 + n/5^2 + n/5^3....
*/
// 复杂度：On
public int trailingZeroes(int n) {
int sum = 0;
// for(int i = 5; i <= n; i++){
// int temp = i;
// while(temp != 0 && temp % 5 == 0){
// sum++;
// temp = temp / 5;
// }
// }
while(n != 0){
sum = sum + n / 5;
n = n / 5;
}
return sum;
}
}
Python
class Solution(object):
def trailingZeroes(self, n):
"""
:type n: int
:rtype: int
"""
sum = 0
# for(int i = 5; i <= n; i++){
# int temp = i;
# while(temp != 0 && temp % 5 == 0){
# sum++;
# temp = temp / 5;
# }
# }
while n != 0:
sum = sum + n // 5
n = n // 5
return sum
C++
class Solution {
public:
int trailingZeroes(int n) {
int sum = 0;
// for(int i = 5; i <= n; i++){
// int temp = i;
// while(temp != 0 && temp % 5 == 0){
// sum++;
// temp = temp / 5;
// }
// }
while (n != 0) {
sum = sum + n / 5;
n = n / 5;
}
return sum;
}
};
Go
func trailingZeroes(n int) int {
sum := 0
// for(int i = 5; i <= n; i++){
// int temp = i;
// while(temp != 0 && temp % 5 == 0){
// sum++;
// temp = temp / 5;
// }
// }
for n != 0 {
sum = sum + n / 5
n = n / 5
}
return sum
}