尾部的零_JAVA_编程开发_程序员俱乐部

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

class="text-sm" style="font-size: 12px;">您在真实的面试中是否遇到过这个题？? 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;
    }

?