lintcode 求n！尾部的零的数目

我不是女神ヾ 2022-06-02 12:48 190阅读 0赞

题目描述大概就是求n的阶乘尾部为零的数目，但是要写成O(logn)的算法复杂度就不简单了。好像lintcode是不能用库的吧？

最傻最傻的做法是真的把n的阶乘求出来，用c++基本不可能，除非用python吧。当然这种算法复杂度可以想像。那就从没有那么傻的作法开始算吧。尾部为零说明是乘了10咯，那么意味着有2和5的因子，很明显2的因子随处可见，那么绝定因素在于5的因子咯。很好，也不用算出阶乘，看乘了多少个5的因子。比如11！，那么就是乘了5和10，一共两个零咯。再比如25！，就5、10、15、20、25。很好25之前的每个算一个因子，25算2个。那么就是6个。具体代码如图：

![Image 1][]![Image 1][]

class Solution {
    public:
        /*
         * @param n: A long integer
         * @return: An integer, denote the number of trailing zeros in n!
         */
        long long trailingZeros(long long n) {
            // write your code here, try to do it without arithmetic operators.
            long long temp;
            long long counter=0;
            for(long long i=5;i<=n;i+=5)
            {
                temp=i;
                while(temp%5==0)
                {
                    counter++;
                    temp/=5;
                }
            
            }
            return counter;
        }
    };

可是这种算法复杂度大概是O(nlogn),我提交了之后才发现要O(logn)的算法复杂度。显然是会超时的。好像只通过了49%的数据。那么就要重新思考了，怎么降低算法复杂度呢，我一开始想到的是递归，他应该有一些递归的规律。不然不可能做到 O(logn)的复杂度的。好吧，用python打印了下各种阶乘，结果发现5的阶乘有1个0，25的阶乘有6个0，125的阶乘有31个0。有没有什么规律呢？不就乘5加1吗？这是为什么呢？原来5=1x5，10=2x5，15=3x5，20=4x5，25=5x5，这下比较清晰了，25多了一个5，乘5加1，很好，那么125呢？不就是5个循环后那个是5x5x5，那么就是6x5+1=31个0咯。好了5的n次方的阶乘的尾部0的个数会了。那么非5的次方呢？还是想了一下。唔，那就化成5的次方相加咯，哈哈，很明显这是五进制。十进制化五进制，很好，仿照十进制化二进制，就不断除5，取余数然后逆序排列就是五进制的数了吧，反正都要用的，那么不用逆序了直接用。至于那个递归的，那么打表比较快吧，预留25位五进制的位数，应该够了吧。那么也不用先打表，边用边打。很棒。代码如下：

class Solution {
    public:
        /*
         * @param n: A long integer
         * @return: An integer, denote the number of trailing zeros in n!
         */
        long long trailingZeros(long long n) {
            // write your code here, try to do it without arithmetic operators.
            if(n<5)return 0;
            if(n==5)return 1;
            long long v[25];
            long long a[25];
            long long sum=0;
            a[0]=0;
            a[1]=1;
            int size=0;
            do
            {
               v[size]=n%5;
               size++;
               n/=5;
            }while(n!=0);
            for(int i=0;i<size;i++)
            {
                if(i==0)continue;
                if(i==1)sum+=a[i]*v[i];
                else
                {
                    a[i]=5*a[i-1]+1;
                    sum+=v[i]*a[i];
                }
            }
            return sum;
        }
    };

这下就是O(logn)的算法复杂度了，应该还可以优化一下，减少时空。代码如下：

class Solution {
    public:
        /*
         * @param n: A long integer
         * @return: An integer, denote the number of trailing zeros in n!
         */
        long long trailingZeros(long long n) {
            // write your code here, try to do it without arithmetic operators.
            if(n<5)return 0;
            if(n==5)return 1;
            long long v;
            long long a[2];
            long long sum=0;
            a[1]=1;
            int size=0;
            do
            {
               v=n%5;
               if(size==1)
               {
                sum+=a[size]*v;
               }
               else if(size>1)
               {
                 a[size%2]=5*a[(size-1)%2]+1;
                 sum+=v*a[size%2];
               }
               size++;
               n/=5;
            }while(n!=0);
            return sum;
        }
    };

貌似少了一个循环，然后空间的利用也少， 从大神舍友哪学来的。问题不大，第一次写博客，排版不好，溜了。

[Image 1]: