LeetCode题解——Factorial Trailing Zeroes

本文主要是介绍LeetCode题解——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的情况是，出现5和2的倍数。

[n/k]代表1~n中能被k整除的个数，而能被2整除的个数多余能被5整除的个数，故只要知道能被5整除的个数即可。那么怎样计算n!的质因子中所有5的个数呢？一个简单的方法是计算floor(n/5)。例如，7!有一个5，10!有两个5。除此之外，还有一件事情要考虑。诸如25，125之类的数字有不止一个5。例如，如果我们考虑28!，我们得到一个额外的5，并且0的总数变成了6。处理这个问题也很简单，首先对n÷5，移除所有的单个5，然后÷25，移除额外的5，以此类推。

n!后缀0的个数 = n!质因子中5的个数
= floor(n/5) + floor(n/25) + floor(n/125) + ....

 ? 
 class  Solution { 
      /* 
      因此只要计数5的个数就可以了。那么怎样计算n!的质因子中所有5的个数呢？ 
      一个简单的方法是计算floor(n/5)。例如，7!有一个5，10!有两个5。 
      除此之外，还有一件事情要考虑。诸如25，125之类的数字有不止一个5。 
      例如，如果我们考虑28!，我们得到一个额外的5，并且0的总数变成了6。 
      处理这个问题也很简单，首先对n÷5，移除所有的单个5，然后÷25，移除额外的5，以此类推。 
      下面是归纳出的计算后缀0的公式。 
      n!后缀0的个数 = n!质因子中5的个数 
                = floor(n/5) + floor(n/25) + floor(n/125) + .... 
      */ 
 public : 
      int  trailingZeroes( int  n) { 
          int  count= 0 ; 
          int  i= 5 ; 
          while (i<=n) 
          { 
              count+=n/i; 
              i*= 5 ; 
          } 
          return  count; 
      } 
 }; //<span background-color:="" font-family:="" font-size:="" helvetica="" line-height:="" style="color:">Time Limit Exceeded  比如输入2147483647 
 </span> 

而另外一种：

 ? 
 class  Solution { 
 public : 
      int  trailingZeroes( int  n) { 
          int  ret =  0 ; 
          while (n) 
          { 
              ret += n/ 5 ; 
              n /=  5 ; 
          } 
          return  ret; 
      } 
 }; //OK 