LeetCode题解：阶乘后的零

题目描述

给定一个整数n，返回n！结果中未随零的数量。
提示n! = n * (n-1) * (n-2) * ……* 2 * 1

示例

• 示例1
  输入：n = 3
  输出：0
  解释：3! = 6 ，不含尾随 0
• 示例2
  输入：n = 5
  输出：1
  解释：5! = 120 ，有一个尾随 0

思路方法

数学

n! 尾零的数量即为 n!中因子 10 的个数，而 10=2×5，因此转换成求 n!中质因子 2 的个数和质因子 5 的个数的较小值。
由于质因子 5 的个数不会大于质因子 2 的个数，我们可以仅考虑质因子 5 的个数。
而 n! 中质因子 5 的个数等于 [1,n] 的每个数的质因子 5 的个数之和，我们可以通过遍历 [1,n] 的所有 5 的倍数求出。

class Solution {
    public int trailingZeroes(int n) {
        int result = 0;
        for(int i=5;i<=n;i+=5){
            for(int j=i;j % 5 ==0;j/=5){
                result++;
            }
        }
        return result;
    }
}

复杂度分析

• 时间复杂度：O(n)
• 空间复杂度：O(1)

优化算法

来自LeetCode解法

class Solution {
    public int trailingZeroes(int n) {
        int result = 0;
        while(n!=0){
            n/=5;
            result+=n;
        }
        return result;
    }
}

复杂度分析

• 时间复杂度：O(logn)
• 空间复杂度：O(1)