Given an integer n, return the number of trailing zeroes in n!.Note: Your solution should be in logarithmic time complexity.

Naive方法：A simple method is to first calculate factorial of n, then count trailing 0s in the result (We can count trailing 0s by repeatedly dividing the factorial by 10 till the remainder is 0). 但這樣做的顯著缺點是：can cause overflow for a slightly bigger numbers as factorial of a number is a big number (See factorial of 20 given in above examples).

轉自GeeksforGeeks的想法：The idea is to considerPRime factorsof a factorial n. A trailing zero is always produced by prime factors 2 and 5. If we can count the number of 5s and 2s, our task is done. Consider the following examples.

n = 5:There is one 5 and 3 2s in prime factors of 5! (2 * 2 * 2 * 3 * 5). So count of trailing 0s is 1.

n = 11:There are two 5s and eight 2s in prime factors of 11! (28* 34* 52* 7). So count of trailing 0s is 2.

我們會發現：the number of 2s in prime factors is always more than or equal to the number of 5s. So if we count 5s in prime factors, we are done.

How to count total number of 5s in prime factors of n!?A simple way is to calculate floor(n/5).

問題轉化為求階乘過程中質因子5的個數，但是要注意25能提供2個5,125能提供3個5....

所以，count=floor(n/5) + floor(n/25) + floor(n/125) + ....

 1 public class Solution { 2     public int trailingZeroes(int n) { 3         int count = 0; 4         for (int i=5; (n/i)>=1;) { 5             count += n / i; 6             n /= 5; 7         } 8         return count; 9     }10 }

最開始我的寫法是：

 1 // Function to return trailing 0s in factorial of n 2 int findTrailingZeros(int  n) 3 { 4     // Initialize result 5     int count = 0; 6   7     // Keep dividing n by powers of 5 and update count 8     for (int i=5; n/i>=1; i *= 5) 9           count += n/i;10  11     return count;12 }

在oj上提交會發現n = 1808548329時出錯了，期望答案是452137076，實際答案是452137080

原因就是 i*5一直連乘時出現i = 5^14時，內存溢出(5^13 = 1220703125 < 2^31, but 5^14 = 6103515625 > 2^32)

Integer overflow之后會wrap around, 即Integer.MAX_VALUE + 1會成為Integer.MIN_VALUE, 詳見Why Integer overflows wrap around

6103515625 wrap around之后 為正的1808548329-1 = 1808548328

原因是6103515625 % 2^32 = 1808548329 < 2 ^31，即 i 比32位Integer（共2^32）多出1808548329個數， 為 1808548328，又可以再進一次for 循環（本不應該進的）。所以答案偏大

解決辦法：用除法代替乘法，用n / 5代替 i * 5，防止overflow，如最上面那段code所示