溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
【題目描述】
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/
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
