题解 | #阶乘末尾0的数量#

阶乘末尾0的数量

http://www.nowcoder.com/practice/aa03dff18376454c9d2e359163bf44b8

阶乘末尾0的数量

问题描述：给定一个非负整数 N，返回N! 结果的末尾为 0的数量。

示例1

输入：3

返回值：0

说明：3！=6

示例2

输入：1000000000

返回值：249999998

方法一

思路分析

通过观察我们发现每一组阶乘会产生0的原因是因为存在 $5\times2=10$ ，一个非负整数的阶乘的末尾0的个数，只需要找到质数相乘的因子中2和5的个数，但由于连续的两个数就存在一个2的因子，因此n的阶乘末尾0的个数只需要找到1~n之间5的个数即可。因此方法是从n开始找到n中质数相乘因子中5的个数，一次遍历到1，但是这种方法时间复杂度高。因此我们让n除以5得到其个数，特别的当有多个因子5时，需要不断的除以5直到n为0为止，在代码中使用while循环，每次将整除后的数赋值给n，直到n为0运行结束。

实例分析

例如： $10!=10\times9\times8\times7\times6\times5\times4\times3\times2\times1$ 末尾0的个数有2个，因为存在2个5

$12!=12\times11\times10\times9\times8\times7\times6\times5\times4\times3\times2\times1$ 末尾0的个数有2个，因为存在2个5

由此我们可以得出只需要找到阶乘中5的个数即可解决问题，即n除以5得到其个数，特别的当有多个因子5时，需要不断的除以5直到n为0为止，在代码中使用while循环，每次将整除后的数赋值给n，直到n为0运行结束。

C++核心代码

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 sum = 0;
        long long base =5;
        while(n)
        {
            sum += n/5;//计算n分解成质数相乘因此中5的个数
            n /= 5;
        }
        return sum;
        
    }
};

复杂度分析

时间复杂度：n不断的除以5寻找次数，因此时间复杂度为 $O(\log_5N)$
空间复杂度: 借助一个辅助变量，空间复杂度为$O(1)$

方法二

思路分析

上面的方法也可以使用递归的思想实现，设置函数$F(n!)$表示n的阶乘末尾0的个数，那么其表达式为$F(n!)=n/5+F((n/5)!)$，因此产生递归的方程，而递归结束的条件为n/5为0，即$n<5$返回0。因此递归公式为：

$n<5 , F(n!)=0$

$n>=5, F(n!)=n/5+F((n/5)!)$

实例分析

$F(100!)=100/5+F((100/5)!)=20+F(20!)=20+4+F(4!)=24$

$F(1000!)=1000/5+F((1000/5)!)=200+F(200!)=240+F(40!)=248+F(8!)=249+0=249$

C++核心代码

class Solution {
public:
    /**
     * the number of 0
     * @param n long长整型 the number
     * @return long长整型
     */
    long long thenumberof0(long long n) {
        // write code here
        if(n<5)//递归结束的条件
            return 0;
        else
            return (n / 5 + thenumberof0(n / 5));//向下递归，不断的整除5
    }
};