一.題目描述
Given an integer n, return the number of trailing zeroes in n!.
Note: Your solution should be in logarithmic time complexity.
二.題目分析
題目的要求是,給定一個整數n
,找出n!
結果的末尾為0
的數的個數。暴力法是首先求出n!
,然後直接計算末尾0
的個數。(重復(n!)/10,直到余數非0為止),若輸入的n
值過大時,在計算階乘時會導致溢出,因此該方法並不好用。
http://www.cnblogs.com/ganganloveu/p/4193373.html 給出一種很巧妙的解決方法:
事實上,只要對n
的階乘n!
,做因數分解:n!=2^x*3^y*5^z*...
顯然0
的個數等於min(x,z)
,並且經證明,可以得到:min(x,z)==z
。
例如:
n = 5
時,5!
的質因數分解:5! = 2 * 2 * 2 * 3 * 5
中包含3
個2
、1
個3
和1
個2
。後綴0
的個數是1
。
n = 11
時,11!
的質因數分解:11! = 2^8 * 3^4 * 5^2 * 7
中包含8
個2
、4
個3
和2
個5
。後綴0
的個數是2
。
證明:
對於階乘而言,也就是1*2*3*...*n
,設[n/k]
代表1~n
中能被k整除的個數
顯然有,[n/2] > [n/5]
(左邊是逢2
增1
,右邊是逢5
增1
)
[n/2^2] > [n/5^2]
(左邊是逢4
增1
,右邊是逢25
增1
)
……
[n/2^p] > [n/5^p]
(左邊是逢2^p
增1
,右邊是逢5^p
增1
)
隨著冪次p
的上升,出現2^p
的概率會遠大於出現5^p
的概率。
因此左邊的加和一定大於右邊的加和,也就是n!
質因數分解中,2
的次冪一定大於5
的次冪。
三.示例代碼
#include
using namespace std;
class Solution{
public:
int trailingZeroes(int n) {
int result = 0;
while (n)
{
result += n / 5;
n /= 5;
}
return result;
}
};
四.小結
這道題的代碼很少,但是要從題目中把復雜的要求轉化為簡單的運算是需要推導的,總體來說還是需要費一定的功夫。