[每日一道小算法（五十五）] [推理] 阶乘后的零（leecode题）

素颜马尾好姑娘i 2023-07-07 03:49 37阅读 0赞

前言：  
今天看了一道特别有意思的题，在这里整理一下，并分享一个我学习到的一位大神的思路。膜拜！！！！[分享链接][Link 1]

### 题目描述 ###

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

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

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

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

### 题目解析 ###

这道题一定要注意这个时间复杂度O（logn）。因为这道题如果直接算，我们都能直到该怎么算，直接求出n的阶乘，然后判断尾数即可。但是这让就会导致溢出的问题。因为阶乘太大会导致溢出。所以不可以使用这个办法，  
下面我们就离开分析比较好的方法：  
比如5的阶乘为120。因为5 \* 4 \* 3 \* 2 \* 1 = 120，我们发现结果会有一个0。原因是2和5相乘构成了一个10。而对于10的话，其实也只有2 \* 5可以构成。那么我们就要找有多少对2/5。  
再来看一例子：11! = 11 \* 10 \* 9 \* 8 \* 7 \* 6 \* 5 \* 4 \* 3 \* 2 \* 1 = 11 \* (2 \* 5) \* 9 \* (4 \* 2) \* 7 \* (3 \* 2) \* (1 \* 5) \* (2 \* 2) \* 3 \* (1 \* 2) \* 1。  
对于含有 2 的因子的话是 1 \* 2, 2 \* 2, 3 \* 2, 4 \* 2 …

对于含有 5 的因子的话是 1 \* 5, 2 \* 5…

对于2的因子每两个出现一次，含有5的因子每5个出现一次，所有2出现的个数远远多于5，换言之找到一个5，一定能找到一个2与之配对。所以我们只需要找多少个5。  
对于一个数的阶乘，就如之前所分析的，5的因子一定是每隔5个数出现一次，也就是这个样子。  
n! = 1 \* 2 \* 3 \* 4 \* (1 \* 5) \* … \* (2 \* 5) \* … \* (3 \* 5) \*… \* n  
每隔5个数出现一个5，所以计算出现了多少个5，我们只需要用n/5就可以出来。  
… \* (1 \* 5) \* … \* (1 \* 5 \* 5) \* … \* (2 \* 5 \* 5) \* … \* (3 \* 5 \* 5) \* … \* n  
每隔25个数字，出现的是两个5，所以每隔5个数做一个5，每隔25个数，还要多算一个5。 此时我们需要 n/5+n/25。  
发现每隔 5 \* 5 \* 5 = 125 个数字，会出现 3 个 5，所以我们还需要再加上 n / 125 。

综上，规律就是每隔 5 个数，出现一个 5，每隔 25 个数，出现 2 个 5，每隔 125 个数，出现 3 个 5… 以此类推。

最终 5 的个数就是 n / 5 + n / 25 + n / 125 …

### 代码样例 ###

package com.asong.leetcode.trailingZeroes;
    
    /** * 阶乘后的0 * 给定一个整数 n，返回 n! 结果尾数中零的数量。 */
    public class Solution { 
        public int trailingZeroes(int n) { 
            int count = 0;
            while(n>0)
            { 
                count += n/5;
                n = n / 5;
            }
            return count;
        }
    }

[Link 1]: https://leetcode-cn.com/problems/factorial-trailing-zeroes/solution/xiang-xi-tong-su-de-si-lu-fen-xi-by-windliang-3/