题解 | #阶乘末尾0的数量#
阶乘末尾0的数量
http://www.nowcoder.com/practice/aa03dff18376454c9d2e359163bf44b8
题意:
- 给定一个非负整数,求该数的阶乘末尾0的数量。
方法一:
- 分析:末尾为0的数量应当取决于质因数5和2的数量,而对于阶乘的数字,显然2的数量在任何情况下都是大于5的数量的,因此直接计算质因数5的数量即可。
- 尝试直接寻找5的数量,遍历含质因数5的数,超时间复杂度。
代码如下:
class Solution { public: /** * the number of 0 * @param n long长整型 the number * @return long长整型 */ long long thenumberof0(long long n) { // write code here long long ans=0; //寻找5的倍数 for(int i=5;i<=n;i+=5){ int tmp=i; //计算出含5的因子个数 while(tmp/5){ ans++; tmp=tmp/5; } } return ans; } };
时间复杂度: , for循环 次,每次for循环内部的while循环是 次,因此加起来是
空间复杂度:。
方法二:
解题思路:
从其他方向分析5的数量规律:
如上,我们发现了规律,即5的数量ans=n/5+n/25+n/125+……,此规律也易证其正确性:
ans=质因子为1个5的数量+质因子为2个5的数量X2+质因子为3个5的数量X3+……+质因子为k个5的数量X5。
n/5=质因子为1个5的数量+质因子为2个5的数量X1+质因子为3个5的数量X1+……+质因子为k个5的数量X1。
n/25=质因子为2个5的数量X1+质因子为3个5的数量X1+……+质因子为k个5的数量X1。
以此类推……
n/(5^k)=质因子为k个5的数量X1。
故ans=n/5+n/25+n/125+……+n/(5^k)如下代码,我们将n循环除以5,第一次更新的n即为n/5的值,即阶乘中含至少一个质因数5的个数。下一次除以5,则阶乘中含至少两个质因数5的个数,以此循环,第i次更新即含至少i个质因数5的个数,累加起来为所求结果。
代码如下:
public: /** * the number of 0 * @param n long长整型 the number * @return long长整型 */ long long thenumberof0(long long n) { // write code here long long ans=0; //将n循环除以5,所得余数即是含5的n次幂的个数。 while(n/5){ n=n/5; ans+=n; } return ans; } };
时间复杂度:,仅一个while循环,每次循环除以5。
空间复杂度:。