【題目描述】
Write an algorithm which computes the number of trailing zeros in n factorial.
設計一個演算法，計算出n階乘中尾部零的個數。
【題目鏈接】
http://www.lintcode.com/en/problem/trailing-zeros/
【題目決議】
傳統解法是首先求出n!，然后計算末尾0的個數。（重復÷10，直到余數非0）該解法在輸入的數字稍大時就會導致階乘得數溢位，不足取。
O（logn）解法：一個更聰明的解法是考慮n!的質數因子。后綴0總是由質因子2和質因子5相乘得來的。如果我們可以計數2和5的個數，問題就解決了。考慮下面的例子：
n = 5: 5!的質因子中 (2 * 2 * 2 * 3 * 5)包含一個5和三個2。因而后綴0的個數是1。
n = 11: 11!的質因子中(2^8 * 3^4 * 5^2 * 7)包含兩個5和三個2。于是后綴0的個數就是2。
我們很容易觀察到質因子中2的個數總是大于等于5的個數。因此只要計數5的個數就可以了。那么怎樣計算n!的質因子中所有5的個數呢？一個簡單的方法是計算floor(n/5)。例如，7!有一個5，10!有兩個5。除此之外，還有一件事情要考慮。諸如25，125之類的數字有不止一個5。例如，如果我們考慮28!，我們得到一個額外的5，并且0的總數變成了6。處理這個問題也很簡單，首先對n÷5，移除所有的單個5，然后÷25，移除額外的5，以此類推。
【參考答案】
http://www.jiuzhang.com/solutions/trailing-zeros/
轉載請註明出處，本文鏈接：https://www.uj5u.com/gongcheng/60946.html
標籤：非技術類