首页 > 代码库 > 《Cracking the Coding Interview》——第17章:普通题——题目3

《Cracking the Coding Interview》——第17章:普通题——题目3

2014-04-28 22:18

题目:计算N的阶乘尾巴上有多少个零?

解法:计算5的个数即可,因为2 * 5 = 10,2的个数肯定比5多。计算5的个数可以在对数时间内搞定。

代码:

 1 // 17.3 Count how many zeros are there in n!?
 2 // Count the number of 5s in n!.
 3 #include <cstdio>
 4 using namespace std;
 5 
 6 int countZero(int n)
 7 {
 8     int res = 0;
 9     
10     while (n > 0) {
11         res += n / 5;
12         n /= 5;
13     }
14     
15     return res;
16 }
17 
18 int main()
19 {
20     int n;
21     
22     
23     while (scanf("%d", &n) == 1) {
24         printf("%d\n", countZero(n));
25     }
26     
27     return 0;
28 }