LeetCode: 172. Factorial Trailing Zeroes

友情支持

如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜

支付宝

有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。

wx jikerizhi

公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。

172. Factorial Trailing Zeroes

LeetCode - Factorial Trailing Zeroes

这个题的解题思路也很精巧，D瓜哥先来举例说明一下。

先来说明一下，产生零的因素：5(乘以2)，10，15………，即 5 的偶数倍。另外，显而易见，偶数比 5 的多很多，所以，我们只需要关注 5 的个数即可。D瓜哥用下面的序列来做进一步分析：

05,10,15,20,25,30,35,40,45,50,55,60,65,70,75,80,85,90,95,100,105,110,115,120,125,130
 ↓  ↓  ↓  ↓  ↓  ↓  ↓  ↓  ↓  ↓  ↓  ↓  ↓  ↓  ↓  ↓  ↓  ↓  ↓   ↓   ↓   ↓   ↓   ↓   ↓   ↓
 1, 2, 3, 4, 5, 6, 7, 8, 9,10,11,12,13,14,15,16,17,18,19, 20, 21, 22, 23, 24, 25, 26
             ↓              ↓              ↓               ↓                   ↓
             1,             2,             3,              4,                  5,
                                                                               ↓
                                                                               1,

为了方便说明，我把第一行做了处理，只关注 5x 的数，每个数都可以产生一个 0。

将第一行的数除以 5，就得到了第二行的数字。这些数字中，一串 5x 的数，每个数又可以产生一个 0。

以此类推，直到最后的序列只剩下不超过 5 截止。上面每行中的 5x 数字的个数就是我们需要的结果：结尾 0 的个数。

思路上，我受到了这详尽的思路令我茅塞顿开！递归非递归都有哦！ - LeetCode Discuss 的启发。但是，自认为比他的解释更容易理解。

Given an integer n, return the number of trailing zeroes in n!.

Example 1:

Input: 3
Output: 0
Explanation: 3! = 6, no trailing zero.

Example 2:

Input: 5
Output: 1
Explanation: 5! = 120, one trailing zero.

*Note: *Your solution should be in logarithmic time complexity.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
/**
 * Runtime: 1 ms, faster than 97.29% of Java online submissions for Factorial Trailing Zeroes.
 *
 * Memory Usage: 34 MB, less than 7.69% of Java online submissions for Factorial Trailing Zeroes.
 */
public int trailingZeroes(int n) {
    int result = 0;
    while (n > 0) {
        result += n / 5;
        n /= 5;
    }
    return result;
}