“给定一个整数n,返回n!结果中尾随零的数量。”
题目链接:
来源:力扣(LeetCode)
给定一个整数 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
这道题要求n!结果中尾随零的数量。
那么先求n!的结果,n! = n * (n - 1) * (n - 2) * ... * 3 * 2 * 1。
求n!的结构其实就是求阶乘的记过,从1到n的连续数相乘的积,叫做阶乘,用符号n!表示。如5!=1×2×3×4×5。规定0!=1。
对于任意一个n!来说,其尾随零的个数是展开式中10的个数决定的,那么求n!尾零的数量就是求n!中因子10的个数,因为10=5X2,那么还可以转化为求n!中质因子2和质因子5的个数的较小值。
由于质因子5的个数不会大于质因子2的个数,所以可以只考虑质因子5,而n!的质因子5的个数等于[1,n]中每个数的质因子5的个数之和,所以可以遍历[1,n]中所有5的倍数求出。
代码参考:
class Solution {
public int trailingZeroes(int n) {
int ans = 0;
for (int i = 5; i <= n; i += 5) {
for (int x = i; x % 5 == 0; x /= 5) {
++ans;
}
}
return ans;
}
}
时间复杂度:O(n)
n!中的质因子5的个数为O(n),因此时间复杂度为O(n)。
空间复杂度:O(1)
只需要常量级的空间。
末尾0其实是任意正整数乘以10产生的,也就是说因子中每出现一个2和一个5,结果就会多一个末尾0。
显然连续数字的阶乘里,2的因子个数是远远多于5的因子个数的。
那么主要影响末尾0的个数其实是5的因子个数。
因此求出质因子5出现的次数就是题目要求的答案。
我的博客即将同步至腾讯云开发者社区,邀请大家一同入驻:https://cloud.tencent.com/developer/support-plan?invite_code=29zkrho922xww