【題目描述】

讓客戶滿意是我們工作的目標(biāo)，不斷超越客戶的期望值來(lái)自于我們對(duì)這個(gè)行業(yè)的熱愛。我們立志把好的技術(shù)通過有效、簡(jiǎn)單的方式提供給客戶，將通過不懈努力成為客戶在信息化領(lǐng)域值得信任、有價(jià)值的長(zhǎng)期合作伙伴，公司提供的服務(wù)項(xiàng)目有：國(guó)際域名空間、網(wǎng)站空間、營(yíng)銷軟件、網(wǎng)站建設(shè)、若羌網(wǎng)站維護(hù)、網(wǎng)站推廣。

Write an algorithm which computes the number of trailing zeros in n factorial.

設(shè)計(jì)一個(gè)算法，計(jì)算出n階乘中尾部零的個(gè)數(shù)。

【題目鏈接】

http://www.lintcode.com/en/problem/trailing-zeros/

【題目解析】

傳統(tǒng)解法是首先求出n!，然后計(jì)算末尾0的個(gè)數(shù)。（重復(fù)÷10，直到余數(shù)非0）該解法在輸入的數(shù)字稍大時(shí)就會(huì)導(dǎo)致階乘得數(shù)溢出，不足取。

O（logn）解法：一個(gè)更聰明的解法是考慮n!的質(zhì)數(shù)因子。后綴0總是由質(zhì)因子2和質(zhì)因子5相乘得來(lái)的。如果我們可以計(jì)數(shù)2和5的個(gè)數(shù)，問題就解決了?？紤]下面的例子：

n = 5: 5!的質(zhì)因子中 (2 * 2 * 2 * 3 * 5)包含一個(gè)5和三個(gè)2。因而后綴0的個(gè)數(shù)是1。

n = 11: 11!的質(zhì)因子中(2^8 * 3^4 * 5^2 * 7)包含兩個(gè)5和三個(gè)2。于是后綴0的個(gè)數(shù)就是2。

我們很容易觀察到質(zhì)因子中2的個(gè)數(shù)總是大于等于5的個(gè)數(shù)。因此只要計(jì)數(shù)5的個(gè)數(shù)就可以了。那么怎樣計(jì)算n!的質(zhì)因子中所有5的個(gè)數(shù)呢？一個(gè)簡(jiǎn)單的方法是計(jì)算floor(n/5)。例如，7!有一個(gè)5，10!有兩個(gè)5。除此之外，還有一件事情要考慮。諸如25，125之類的數(shù)字有不止一個(gè)5。例如，如果我們考慮28!，我們得到一個(gè)額外的5，并且0的總數(shù)變成了6。處理這個(gè)問題也很簡(jiǎn)單，首先對(duì)n÷5，移除所有的單個(gè)5，然后÷25，移除額外的5，以此類推。

【參考答案】

http://www.jiuzhang.com/solutions/trailing-zeros/

另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務(wù)器15元起步，三天無(wú)理由+7*72小時(shí)售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國(guó)服務(wù)器、虛擬主機(jī)、免備案服務(wù)器”等云主機(jī)租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡(jiǎn)單易用、服務(wù)可用性高、性價(jià)比高”等特點(diǎn)與優(yōu)勢(shì)，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場(chǎng)景需求。

文章名稱：Lintcode2TrailingZerossolution題解-創(chuàng)新互聯(lián)
標(biāo)題URL：http://weahome.cn/article/cssjse.html