大家好,我是小魔龙,Unity3D软件工程师,VR、AR,虚拟仿真方向,不定时更新软件开发技巧,生活感悟,觉得有用记得一键三连哦。
一、题目
1、算法题目
“给定一个整数n,返回n!结果中尾随零的数量。”
2、题目描述
给定一个整数 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
二、解题
1、思路分析
这道题要求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的倍数求出。
2、代码实现
代码参考:
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; } }
3、时间复杂度
时间复杂度:O(n)
n!中的质因子5的个数为O(n),因此时间复杂度为O(n)。
空间复杂度:O(1)
只需要常量级的空间。
三、总结
末尾0其实是任意正整数乘以10产生的,也就是说因子中每出现一个2和一个5,结果就会多一个末尾0。
显然连续数字的阶乘里,2的因子个数是远远多于5的因子个数的。
那么主要影响末尾0的个数其实是5的因子个数。
因此求出质因子5出现的次数就是题目要求的答案。