☆打卡算法☆LeetCode 172. 阶乘后的零 算法解析

一、题目

1、算法题目

“给定一个整数n，返回n!结果中尾随零的数量。”

题目链接：

来源：力扣（LeetCode）

链接： 172. 阶乘后的零 - 力扣（LeetCode）

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;
    }
}

image.png

3、时间复杂度

时间复杂度：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