【leetcode】172. 阶乘后的零( Factorial Trailing Zeroes )


题目描述

【leetcode】172. 阶乘后的零( Factorial Trailing Zeroes )
给定一个整数 n,返回 n! 结果尾数中零的数量。
说明: 你算法的时间复杂度应为 O(log n) 。
【leetcode】172. 阶乘后的零( Factorial Trailing Zeroes )

错误的思路1:

n!展开过程中,每次相乘时,尾数0的数量只与最后一位非0值有关,
所以每次相乘后累加末尾0的个数,然后只取最靠右的非0值。
这种想法是错的,反例 25*4=100,有2个0,若只考虑最靠右非0值,只能得到1个0

错误的思路2:

末尾0的数量即为1,2,3,…,n中因子5的个数,而因子5的个数即为下列数列和: int(n/5),int(n/52),...,int(n/5num)int(n/5),int(n/5^2),...,int(n/5^{num})int(n/5),int(n/52),...,int(n/5num) 。其中项数 num=int(lg(n)/lg(5))num = int(lg(n)/lg(5))num=int(lg(n)/lg(5)) ;
上面的数列似乎是等比数列前n项和的形式,但是请注意,其中每一项都带了int(),即向下取整,所以把它当作等比数列的画会引入误差积累,计算到某些输入值会出错,但是还是想讨论一下。
若不考虑int()带来的误差,则 Sn=a1(1qn)/(1q)Sn = a_1(1-q^n)/(1-q)Sn=a1​(1−qn)/(1−q) ;,注意,由上面推导,Sn必定是整数,例如Sn=49。由于q=1/5为浮点数,导致Sn计算将导致误差,Sn可能为48.999,或者是49.0001。所以我们需要把Sn式子分子分母同乘以q^n,变形为无浮点数的运算, Sn=a1(5n1)/(45n1)Sn = a_1(5^n-1)/(4*5^{n-1})Sn=a1​(5n−1)/(4∗5n−1) ;
错误的思路2的代码:

#include <cmath>
class Solution {
public:
    int trailingZeroes(int n) {
        if(0 == n)
            return 0;
        
        int num = log(n)/log(5);
        int a1 = n/5;
        // double q = 1/5.0;
        // int count = a1*(1-1/pow(5,num))/(1-q) ;
        int count = a1*(pow(5,num)-1)/(4*pow(5,num-1));
		return count;
};

第一次解答

思路:
阶乘n!中末尾0的数量 等于 阶乘n!中因子10的数量 进而等于 阶乘中因子2和因子5的成对出现的次数,因为因子2需要每递增2就至少新增一个,而因子5需要每递增5才至少出现一个,所以2的数量远比5的数量多,因此,又有
阶乘n!中末尾0的数量 等于 阶乘n!中因子5的数量
到这里已经可以直接求解,但是若是遍历1-n去寻找所有因子5,时间复杂度为nlogn,能否有更简单的方法?答案当然是有。
通过观察可得出,阶乘n!中因子5的数量 即为下列数列和: int(n/5),int(n/52),...,int(n/5num)int(n/5),int(n/5^2),...,int(n/5^{num})int(n/5),int(n/52),...,int(n/5num)
其中,项数 num=int(log5(n))num = int(log_5(n))num=int(log5​(n)) 。请注意,其中每一项都带了int(),即向下取整,所以把它当作等比数列的画会引入误差积累,所以我们不能直接利用等比数列前n项和计算结果,需要用程序展开计算每一项,时间复杂度为log5(n)log_5(n)log5​(n)即O(log n)。
test case:
5
0
1
200

class Solution {
public:
    int trailingZeroes(int n) {
        int count = 0;
        while(n>4){
            n = n/5;
            count += n;
        }
        return count;
    }
};

结果:
【leetcode】172. 阶乘后的零( Factorial Trailing Zeroes )

相关/参考链接

参考1
参考2

【leetcode】172. 阶乘后的零( Factorial Trailing Zeroes )【leetcode】172. 阶乘后的零( Factorial Trailing Zeroes ) LiBer_CV 发布了79 篇原创文章 · 获赞 61 · 访问量 2万+ 私信 关注
上一篇:Codeforces Round #588 (Div. 2) B. Ania and Minimizing(构造)


下一篇:B. Ania and Minimizing (Codeforces Round #588 (Div. 2) )