# 0172. 階乘后的零 ## 題目地址(172. 階乘后的零) <https://leetcode-cn.com/problems/factorial-trailing-zeroes/> ## 題目描述 ``` <pre class="calibre18">``` 給定一個整數 n，返回 n! 結果尾數中零的數量。 示例 1: 輸入: 3 輸出: 0 解釋: 3! = 6, 尾數中沒有零。 示例 2: 輸入: 5 輸出: 1 解釋: 5! = 120, 尾數中有 1 個零. 說明: 你算法的時間復雜度應為 O(log n) 。 ``` ``` ## 前置知識 - [遞歸](https://github.com/azl397985856/leetcode/blob/master/thinkings/basic-data-structure.md) ## 公司 - 阿里 - 騰訊 - 百度 - bloomberg ## 思路 我們需要求解這n個數字相乘的結果末尾有多少個0，由于題目要求log的復雜度，因此暴力求解是不行的。 通過觀察，我們發現如果想要結果末尾是0，必須是分解質因數之后，2 和 5 相乘才行，同時因數分解之后發現5的個數遠小于2， 因此我們只需要求解這n數字分解質因數之后一共有多少個5即可.  如圖如果n為30，那么結果應該是圖中紅色5的個數，即7。  我們的結果并不是直接f(n) = n / 5, 比如n為30， 25中是有兩個5的。 類似，n為150，會有7個這樣的數字，通過觀察我們發現規律`f(n) = n/5 + n/5^2 + n/5^3 + n/5^4 + n/5^5+..`  如果可以發現上面的規律，用遞歸還是循環實現這個算式就看你的了。 ## 關鍵點解析 - 數論 ## 代碼 - 語言支持：JS，Python Javascript Code: ``` <pre class="calibre18">``` <span class="hljs-title">/* * @lc app=leetcode id=172 lang=javascript * * [172] Factorial Trailing Zeroes */</span> <span class="hljs-title">/** * @param {number} n * @return {number} */</span> <span class="hljs-keyword">var</span> trailingZeroes = <span class="hljs-function"><span class="hljs-keyword">function</span>(<span class="hljs-params">n</span>) </span>{ <span class="hljs-title">// tag: 數論</span> <span class="hljs-title">// if (n === 0) return n;</span> <span class="hljs-title">// 遞歸： f(n) = n / 5 + f(n / 5)</span> <span class="hljs-title">// return Math.floor(n / 5) + trailingZeroes(Math.floor(n / 5));</span> <span class="hljs-keyword">let</span> count = <span class="hljs-params">0</span>; <span class="hljs-keyword">while</span> (n >= <span class="hljs-params">5</span>) { count += <span class="hljs-params">Math</span>.floor(n / <span class="hljs-params">5</span>); n = <span class="hljs-params">Math</span>.floor(n / <span class="hljs-params">5</span>); } <span class="hljs-keyword">return</span> count; }; ``` ``` Python Code: ``` <pre class="calibre18">``` <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">trailingZeroes</span><span class="hljs-params">(self, n: int)</span> -> int:</span> count = <span class="hljs-params">0</span> <span class="hljs-keyword">while</span> n >= <span class="hljs-params">5</span>: n = n // <span class="hljs-params">5</span> count += n <span class="hljs-keyword">return</span> count <span class="hljs-title"># 遞歸</span> <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">trailingZeroes</span><span class="hljs-params">(self, n: int)</span> -> int:</span> <span class="hljs-keyword">if</span> n == <span class="hljs-params">0</span>: <span class="hljs-keyword">return</span> <span class="hljs-params">0</span> <span class="hljs-keyword">return</span> n // <span class="hljs-params">5</span> + self.trailingZeroes(n // <span class="hljs-params">5</span>) ``` ``` **復雜度分析** - 時間復雜度：O(logN)O(logN)O(logN) - 空間復雜度：O(1)O(1)O(1) 更多題解可以訪問我的LeetCode題解倉庫：<https://github.com/azl397985856/leetcode> 。 目前已經37K star啦。 關注公眾號力扣加加，努力用清晰直白的語言還原解題思路，并且有大量圖解，手把手教你識別套路，高效刷題。