尾部的零

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

您在真实的面试中是否遇到过这个题？ 

Yes

样例

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

 

 

题目地址

这一题，看着很水，但是要是没有做过的话，也会 遇到很多的坑，我就是这样（难受），这道题虽然非常简单，但是非常的考察人，第一种算法就是最low，最暴力的方法，简单粗暴的计算能被分解的5的个数：

public static long num(long n){

        if (n < 5){
            return 0;
        }
        long num = 0;
        for (long i = 5;i <= n;i++){
            long t = i;
            while (t%10==0&&t!=0){
                num++;
                t = t/10;
            }

            while (t%5 == 0&&t!=0){
                num++;
                t = t/5;
            }
        }
        return num;
    }

 这种算法的复杂度是0（n）,很明显 超时了；

我就想要是我把每次的步数调整为5那时间复杂度不就是O(n)/5

public static long num(long n){

        if (n < 5){
            return 0;
        }
        long num = 0;
        for (long i = 5;i <= n;i+=5){
            long t = i;
            while (t%10==0&&t!=0){
                num++;
                t = t/10;
            }

            while (t%5 == 0&&t!=0){
                num++;
                t = t/5;
            }
        }
        return num;
    }

 可是我又天真了，还是超时，因为O(n)约等于O(n)/5;

最后参考了一下某网友的方法如下：

    public static long num(long n){
         long num = 0;
         long t = n/5;
         while (t!=0){
             num+=t;
             t = t/5;
        }
        return num;
    }

 这个算法的时间复杂度为O(n);

我又写了下面同样 复杂度的方法：

    public static long num(long n){
          long num = 0;
          while (n!=0){
              long t = n/5;
              num+=t;
              n = n/5;
        }
        return num;
    }