尾部的零

题目

求给定自然数n阶乘结果末尾0的数量,原题链接
http://www.lintcode.com/zh-cn/problem/trailing-zeros/

分析

对于阶乘运算n!=n*(n-1)*(n-2)*...*2*1,其结果末尾的0,都是通过乘以10的倍数、5的倍数得到的,其实10的倍数,也就是5的倍数,由于因子2十分充裕,因此,这道题目的问题其实就是在问,从1~n,每个数可以分解出来的5的个数之和是多少。举个例子,10!= 1*2*...*9*10,其中10=2*5,因此10!包含2个5,其结果尾数的0必然有2个。

初步方案

通过之前的分析,就可以得到一个初步方案了,方案如下:

  • 遍历1~n的所有自然数,计算其分解因式时包含5的个数
  • 累加的结果就是最后末尾0的数量
  • 再进一步,并不需要考察所有1~n之间的数,令i为正整数,对于不超过n的所有5i的数进行因式分解即可
    根据上述分析的代码实现如下

long count(long val){
    long counter = 0;
    while(val % 5 == 0){
        counter++;
        val = val / 5;
    }
    return counter;
}

long trailingZeros(long n) {
    long result = 0;
    for(long i=5; i<=n; i+=5){
        result += count(i);
    }
}

进一步优化

之前的方案已经可以正确得到结果,但其效率在n取值较大时不高,在lintcode上提交会导致运算超时,那么是否还存在更高效的解法?答案必须是肯定的。

每5个连续的自然数中,就必然包含一个5的倍数,故而1~n中,能被5整除的数共有[n/5]个,将这些数分别记为A = {a1,a2,...,a[n/5]},还能因式分解出5的数,皆在A中,如何计算A中还能分解出多少5呢?拿一个实例试一试,令n=27,可知A={5, 10, 15, 20, 25},由于A中元素已经计算过一次5的倍数,对A中元素都除以5,得到新的A={1,2,3,4,5},A此时就变成了一个新的阶乘(n/5)!,此时就递归成了原来的问题!因此,我们得出结论:

  • 对于任意一个阶乘n!,其中5的倍数共有n/5个
  • 1~n中凡是5的倍数的数,除以5后可以得到一个新的阶乘 [n/5]!
  • 重复上述两个步骤,即可求出1~n中能分解出来5的个数

最终代码如下:


     long n5count(long n){
        return n/5;
     }
     
     long trailingZeros(long n) {
       long total = n/5;
       long set = n/5;
       while(set > 0){
          total += n5count(set);
          set = set/5;
       }
       return total;
      }

优化后的方案,明显好于最初的算法。新方案不再逐一判断每一个数,而是将阶乘作为整体考虑,效率得到了明显的提升。

Show Comments

Get the latest posts delivered right to your inbox.