# Factorial Trailing Zeroes ### Source - leetcode: [Factorial Trailing Zeroes | LeetCode OJ](https://leetcode.com/problems/factorial-trailing-zeroes/) - lintcode: [(2) Trailing Zeros](http://www.lintcode.com/en/problem/trailing-zeros/) ~~~ Write an algorithm which computes the number of trailing zeros in n factorial. Example 11! = 39916800, so the out should be 2 Challenge O(log N) time ~~~ ### 題解1 - Iterative 找階乘數中末尾的連零數量，容易想到的是找相乘能為10的整數倍的數，如 2×52 \times 52×5, 1×101 \times 101×10 等，遙想當初做阿里筆試題時遇到過類似的題，當時想著算算5和10的個數就好了，可萬萬沒想到啊，25可以變為兩個5相乘！真是蠢死了... 根據數論里面的知識，任何正整數都可以表示為它的質因數的乘積[wikipedia](#)。所以比較準確的思路應該是計算質因數5和2的個數，取小的即可。質因數2的個數顯然要大于5的個數，故只需要計算給定階乘數中質因數中5的個數即可。原題的問題即轉化為求階乘數中質因數5的個數，首先可以試著分析下100以內的數，再試試100以上的數，聰明的你一定想到了可以使用求余求模等方法 :) ### Python ~~~ class Solution: # @param {integer} n # @return {integer} def trailingZeroes(self, n): if n < 0: return -1 count = 0 while n > 0: n /= 5 count += n return count ~~~ ### C++ ~~~ class Solution { public: int trailingZeroes(int n) { if (n < 0) { return -1; } int count = 0; for (; n > 0; n /= 5) { count += (n / 5); } return count; } }; ~~~ ### Java ~~~ public class Solution { public int trailingZeroes(int n) { if (n < 0) { return -1; } int count = 0; for (; n > 0; n /= 5) { count += (n / 5); } return count; } } ~~~ ### 源碼分析 1. 異常處理，小于0的數返回-1. 1. 先計算5的正整數冪都有哪些，不斷使用 n / 5 即可知質因數5的個數。 1. 在循環時使用 `n /= 5` 而不是 `i *= 5`, 可有效防止溢出。 ****> lintcode 和 leetcode 上的方法名不一樣，在兩個 OJ 上分別提交的時候稍微注意下。 ### 復雜度分析 關鍵在于`n /= 5`執行的次數，時間復雜度 log5n\log_5 nlog5n，使用了`count`作為返回值，空間復雜度 O(1)O(1)O(1). ### 題解2 - Recursive 可以使用迭代處理的程序往往用遞歸，而且往往更為優雅。遞歸的終止條件為`n <= 0`. ### Python ~~~ class Solution: # @param {integer} n # @return {integer} def trailingZeroes(self, n): if n == 0: return 0 elif n < 0: return -1 else: return n / 5 + self.trailingZeroes(n / 5) ~~~ ### C++ ~~~ class Solution { public: int trailingZeroes(int n) { if (n == 0) { return 0; } else if (n < 0) { return -1; } else { return n / 5 + trailingZeroes(n / 5); } } }; ~~~ ### Java ~~~ public class Solution { public int trailingZeroes(int n) { if (n == 0) { return 0; } else if (n < 0) { return -1; } else { return n / 5 + trailingZeroes(n / 5); } } } ~~~ ### 源碼分析 這里將負數輸入視為異常，返回-1而不是0. 注意使用遞歸時務必注意收斂和終止條件的返回值。這里遞歸層數最多不超過 log5n\log_5 nlog5n, 因此效率還是比較高的。 ### 復雜度分析 遞歸層數最大為 log5n\log_5 nlog5n, 返回值均在棧上，可以認為沒有使用輔助的堆空間。 ### Reference - wikipedia > . [Prime factor - Wikipedia, the free encyclopedia](http://en.wikipedia.org/wiki/Prime_factor)[ ?](# "Jump back to footnote [wikipedia] in the text.") - [Count trailing zeroes in factorial of a number - GeeksforGeeks](http://www.geeksforgeeks.org/count-trailing-zeroes-factorial-number/)