lintcode第二题 计算n阶乘中尾部零的个数

原文地址：http://blog.csdn.net/surp2011

正文

题目

设计一个算法，计算出n阶乘中尾部零的个数

样例 
11! = 39916800，因此应该返回 2

挑战 
O(logN)的时间复杂度

题目分析

先说结论，此问题大致有三种思路：第一种算出结果，然后查看末尾的0的个数，效果非常差；第二种，加法操作，从5开始，每次进5，然后判断，效果达不到O(logN)；第三种，每次除5，多次之后结束。 
详情如下。

重点分析在算法2和算法3，需要的可以直接跳到这部分查看。

算法1：最朴素

面对此问题，第一反应是直接计算结果：11!=39916800，然后设计程序判断末尾的0的个数，很简单就可以实现。 
但是相应的会有很多的问题： 
1、计算阶乘的开销 
现在只是11的阶乘，都已经很大了，如果是5555550000000的阶乘呢？按照程序的计算结果，末尾会有1388887499996个0，计算开销很值得考虑。 
2、溢出 
按照上面的介绍，5555550000000的阶乘有1388887499996个0，那么可以推知阶乘的结果会是很大的一个整数，肯定会超出long类型的界限，结果会溢出。这样还要考虑处理溢出问题，又是另一个问题。 
3、效率 
算法2会涉及到效率问题，会发现即使是算法2也会出现计算时间超出要求的问题，那么更为“朴素”的算法1效率更是可想而知了。 
因此，算法1，舍弃。

算法2：以5为迭代步数

算法2分析

仔细的考虑问题，会发现末尾出现的0是10或10的倍数相乘的结果，而10其实是5与偶数相乘。也就是，最终结果中末尾出现的0是5、10、15、20、25…自身或与偶数相乘之后的产生的。下面可以分为偶数和5的倍数分析。

首先考虑偶数。 
考虑2的幂次项2、4、8…中的2的个数，发现2的幂指数的增长速度远比5的幂指数增长的快，更不用说其他的普通偶数6、12、14…。因此可以认为有足够的偶数与奇数形式的5的倍数相乘产生足够的0。所以我们后面只考虑5的倍数。

接着考虑5的倍数。

1、2、3、4、5、6、7、8、9、10、11...

• 1

其实1、2、3、4、6、7…都是可以不用考虑的，因此选择以5为迭代步数即可。 
首先，这些数字都可以不用进行%5（对5取余数）运算，因此每次循环时可以直接将函数的count变量直接加1。其次，考虑25、125、625…等5的幂次项，因为他们每一个都可以在与偶数相乘之后产生多个0。因此，设置一个循环体，判断是多少幂次项，并将结果加进count。 
综上所述，可以编写代码如下：

算法2代码

public class Solution {

    /*
     * param n: As desciption return: An integer, denote the number of trailing
     * zeros in n!
     */
    public long trailingZeros(long n) {
        // write your code here
        long count = 0;
        long pwr = 25;
        for (long temp = 5; temp <= n; temp+=5) {
            // for循环内部的temp都是5的倍数，因此首先进行+1操作
            count++;
            pwr = 25;
            // 判断是不是25、125、625...的倍数，并根据每次pwr的变化进行+1操作
            while (temp % pwr == 0) {
                count++;
                pwr *= 5;
            }
        }
        return count;
    }
}

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22
• 23

代码很简单，不再解释。 
但是效率很差，分析发现代码的时间复杂度实际是O(N/5)~=O(N)，达不到要求的O(logN)。 
算法2虽然可以解决问题，但考虑执行效率，算法2应该舍弃。

算法3：科学思想

反思&对比

这个算法真的是感触很深，对平时很多习以为常的公式、道理有了非常直观的认识，因此对自己的冲击很大，也促进了思考的进步。

提交算法2的代码，发现前面的简单测试都能通过，但是数值5555550000000测试失败。特别是实现了时间复杂度O(logN)的算法3之后，才发现两者时间开销差别真的是很大。

重新分析

1、2、3、4、5、6、7、8、9、10、11、...

• 1

1、分析上面的数列可知，每5个数中会出现一个可以产生结果中0的数字。把这些数字抽取出来是：

...、5、...、10、...、15、...、20、...、25、...

• 1

这些数字其实是都能满足5*k的数字，是5的倍数。统计一下他们的数量：n1=N/5。比如如果是101，则101之前应该是5,10,15,20,...,95,100共101/5=20个数字满足要求。

整除操作满足上面的数量统计要求。

2、将1中的这些数字化成5*(1、2、3、4、5、...)的形式，内部的1、2、3、4、5、...又满足上面的分析：每5个数字有一个是5的倍数。抽取为：

...、25、...、50、...、75、...、100、...、125、...

• 1

而这些数字都是25的倍数（5的2次幂的倍数），自然也都满足5*k的要求。 
这些数字是25、50、75、100、125、...=5*(5、10、15、20、25、...)=5*5*(1、2、3、4、5、...)，内部的1、2、3、4、5、...又满足上面的分析，因此后续的操作重复上述步骤即可。 
统计一下第二次中满足条件的数字数量：n2=N/5/5，101/25=(101/5)/5=4。 
因为25、50、75、100、125、...它们都满足相乘后产生至少两个0，在第一次5*k分析中已经统计过一次。对于N=101，是20。因此此处的5*5*k只要统计一次4即可，不需要根据25是5的二次幂统计两次。 
后面的125,250,...等乘积为1000的可以为结果贡献3个0的数字，只要在5*5*k的基础上再统计一次n3=((N/5)/5)/5即可。 

3、第三次 
其实到这里已经不用再写，规律已经很清楚了。对于例子N=101，只要根据规律进行101/125=((101/5)/5)/5=4/5=0，退出统计。因此最终结果是20+4=24。计算结束。

算法3代码

下面编写打码实现上面的思想。

public class Solution {

    /*
     * param n: As desciption return: An integer, denote the number of trailing
     * zeros in n!
     */
    public long trailingZeros(long n) {
        // write your code here
        long count = 0;
        long temp=n/5;
        while (temp!=0) {
            count+=temp;
            temp/=5;
        }
        return count;
    }
}

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17

代码分析： 
算法中每次循环均有除以5的操作，也就是每次都会将所要处理的数据量缩小至上一次的1/5，容易推知时间复杂度为O(logN)。

至此，问题解决。

tips

关于测试代码，按照上一篇文章的介绍，如果使用Main函数调用Solution:trailingZeros()函数，在传入参数较小的时候，不会有什么问题，如下：

public class Test{
    public static void main(String args[]){
        Solution s=new Solution();
        long result=s.trailingZeros(11);
        System.out.println(result);
    }
}

• 1
• 2
• 3
• 4
• 5
• 6
• 7

因为11不超过int类型的最大长度，所以并不会报错。但是如果是5555550000000，则会报错:

The literal 5555550000000 of type int is out of range 

• 1

将数值进行强制类型转换也不行：long inNum=(long)5555550000000;。 
一种解决方法是使用Scanner直接读取数值。 
改进后的代码如下：

public class Test{
    public static void main(String args[]){
        Solution s=new Solution();
        Scanner scanner=new Scanner(System.in);
        long result=s.trailingZeros(scanner.nextLong());
        System.out.println(result);
    }
}

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8

这时输入5555550000000则不会报错。 
另外，如果需要的话，可使用System.currentTimeMillis();观察代码执行时间。

小结

从最终的代码来看，问题是挺简单的。之所以折腾这么久都没有切入要害，直接做到真正的时间复杂度为O(logN)的效果，个人觉得是因为从分析题目的时候就没有真正理解O(logN)的真正含义。 
类似于二叉搜索树，从根节点开始比较，比根节点小则与左子树比较，比根节点大则与右子树比较，相等或到达叶子节点则退出。如此循环迭代。 
每次判断后，下一次可搜索的数据量均为上一次的1/2，如此循环复杂度为O(logN)。