时间戳

首页 > 技术文章 > 【leetcode】Factorial Trailing Zeroes

【leetcode】Factorial Trailing Zeroes

reachteam 2014-12-30 16:52 原文

Factorial Trailing Zeroes

Given an integer n, return the number of trailing zeroes in n!.

Note: Your solution should be in logarithmic time complexity.

 

统计末尾0的个数，只需要统计2，5的个数就可以了

 

 1 class Solution {
 2 public:
 3     int trailingZeroes(int n) {
 4         
 5         int count2=0;
 6         int count5=0;
 7         
 8         for(int i=2;i<=n;i++)
 9         {
10             int num=i;
11             while(num%2==0&&num>0)
12             {
13                 count2++;
14                 num=num/2;
15             }
16         
17         
18             while(num%5==0&&num>0)
19             {
20                 count5++;
21                 num=num/5;
22             }
23         }
24          
25         return min(count2,count5);
26     }
27 };

 

[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的上升，[n/2^p]会远大于[n/5^p]
因此左边的加和一定大于右边的加和，也就是n!质因数分解中，2的次幂一定大于5的次幂

（感谢陆草纯博主的证明）
 
5的个数显然要比2的个数多，所以只统计5的个数就可以了
 1 class Solution {
 2 public:
 3     int trailingZeroes(int n) {
 4        
 5         int count2=0;
 6         int count5=0;
 7        
 8         for(int i=2;i<=n;i++)
 9         {
10             int num=i;
11            
12             while(num%5==0&&num>0)
13             {
14                 count5++;
15                 num=num/5;
16             }
17         }
18        
19         return count5;
20     }
21 };

 

 
 
既然只要统计5的个数就可以了，那么假设n=100，考虑有多少个5,
1~100里面有
1*5,2*5,3*5……20*5
 
通过上面的式子我们可以找到20个5
并且1-20之中也是存在5的，
1*5，2*5，3*5，4*5
又找到了4个5
而1-4之中就没有5了，因此共有24个5
 
可以抽象成下面的递归算法
 
 1 class Solution {
 2 public:
 3     int trailingZeroes(int n) {
 4         return get5(n);
 5     }
 6    
 7     int get5(int n)
 8     {
 9         if(n<5)return 0;
10         return n/5+get5(n/5);
11     }
12 };

 

推荐阅读