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

桃扇骨 2022-05-19 07:21 173阅读 0赞

这里我们知道，大家最平常的思维就是用一个数来接收n阶乘后的数，然后再来判断那个和的尾部的0的个数，这样的算法算得上O（n）级，还有一个隐患，就是就算用long来存储数据，也不会太长，20的阶乘都不好估计就崩了，所以这种算法不可取。

我们这次来实现一个O（n/5）的算法，这个算法比较好理解。

我们可以知道，n的阶乘的尾部为0的个数主要取决于其中5的个数，例如看下面这个图

![70][]

其实也就是寻找5 的个数，有一个5，也就意味这多了一个0，要注意5的幂数，25,125,625这些数要注意就行，下面我们看代码：

public long trailingZeros1(long n) {
        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;
    }

其实这种算法，还不算是级别最高的，当你输入一个很大的数值时，这种算法就有了一个挺大的瓶颈。下面我们实现一个比较厉害的O（logN）的算法。

我们先来看代码把，看完了在分析：

public static long trailingZeros(long n) {
        // write your code here
        long count = 0;
        long temp=n/5;
        while (temp!=0) {
            count+=temp;
            temp/=5;
        }
        return count;
    }

这个算法的级别就很高了，这个其实就是一个简单的找规律的问题：

![70 1][]

我们这个代码就是实现了这个规律。

[70]: /images/20220519/445ca59494c940e1b9fbefc43e6dd26a.png
[70 1]: /images/20220519/5ca85d908e624c13a5ae3ca6c2f80ece.png