LeetCode 172: Factorial Trailing Zeroes

发表于 | | 阅读次数:
字数统计: 241 | 阅读时长 ≈ 1

题目链接

https://leetcode-cn.com/problems/factorial-trailing-zeroes/

题意

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

示例 1:

输入: 3
输出: 0
解释: 3! = 6, 尾数中没有零。

示例 2:

输入: 5
输出: 1
解释: 5! = 120, 尾数中有 1 个零.

说明: 你算法的时间复杂度应为 O(log n) 。

题目类型

数学

题目分析

以前对这道题一直有误解，今天才发现标解做个记号留存一下。
n!的末置0都是由2*5来的，所以只要统计1n的数中含因子5的个数就够了，因为2明显比5多得多。
统计的方法也很巧妙，1n中含因子5的个数就是n/5，因为有含2个3个因子5的情况，所以答案为$n/5 + n / 5 ^ 2 + n / 5 ^ 3$…

时间复杂度

$O(log _{2} n)$

源代码

1
2
3
4
5
6
class Solution {
public:
    int trailingZeroes(int n) {
        return n == 0 ? 0 : n / 5 + trailingZeroes(n / 5);
    }
};
0%