題目來源于 LeetCode 上第 172 號問題：階乘后的零。題目難度為 Easy，目前通過率為 38.0% 。

題目描述

給定一個整數?n，返回?n! 結果尾數中零的數量。

示例 1:

輸入: 3輸出: 0解釋: 3! = 6, 尾數中沒有零。

示例 2:

輸入: 5輸出: 1解釋: 5! = 120, 尾數中有 1 個零.

說明:?你算法的時間復雜度應為?O(log?n) 。

題目解析

題目很好理解，數階乘后的數字末尾有多少個零。

最簡單粗暴的方法就是先乘完再說，然后一個一個數。

事實上，你在使用暴力破解法的過程中就能發(fā)現規(guī)律：?這 9 個數字中只有 2（它的倍數） 與 5 （它的倍數）相乘才有 0 出現。

所以，現在問題就變成了這個階乘數中能配?多少對 2 與 5。

舉個復雜點的例子：

10！ = 【 2 *（ 2 * 2 ）* 5 *（ 2 * 3 ）*（ 2 * 2 * 2 ）*（ 2 * 5）】

在 10！這個階乘數中可以匹配兩對 2 * 5 ，所以10！末尾有 2 個 0。

可以發(fā)現，一個數字進行拆分后 2 的個數肯定是大于 5 的個數的，所以能匹配多少對取決于 5 的個數。（好比現在男女比例懸殊，最多能有多少對異性情侶取決于女生的多少）。

那么問題又變成了?統(tǒng)計階乘數里有多少個 5 這個因子。

需要注意的是，像 25，125 這樣的不只含有一個 5 的數字的情況需要考慮進去。

比如?n = 15。那么在?15!?中 有?3?個?5?(來自其中的5,?10,?15)， 所以計算?n/5?就可以 。

但是比如?n=25，依舊計算?n/5?，可以得到?5?個5，分別來自其中的5, 10, 15, 20, 25，但是在?25?中其實是包含?2個?5?的，這一點需要注意。

所以除了計算?n/5?， 還要計算?n/5/5 , n/5/5/5 , n/5/5/5/5 , ..., n/5/5/5,,,/5直到商為0，然后求和即可。

代碼實現

public class Solution { ??

?public int trailingZeroes(int n) { ?

? ? ?return n == 0 ? 0 : n / 5 + trailingZeroes(n / 5); ??

?}}