Blog Content

Lintcode-2:尾部的零

每日一练 算法 C/C++ LintCode   2010-03-02 22:23:05

---

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

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

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

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

n的阶乘即从1连乘到n的积，尾部0的个数只会由因数2与5的乘积产生，对任意i*2^j都会有小于该数的i*5^j，故因数2的个数>=因素5的个数，所以只需统计因数5^j的个数即可。如果直接计算因数5^2的个数，则算法复杂度较高，那采用什么方法可以降低算法复杂度呢？如下：

对n除5整除，得出因数5的个数；再除5，得出因数25的个数；……；然后累加。
这样i*5^j这个数即会被累加j次，最终1…n中所有5^j次方因数都被累计出来，即可得到最终结果。

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

#include 

long trailingZeros(long n) {
    // 算法中每次循环均有除以5的操作，也就是每次都会将所要处理的数据量缩小至上一次的1/5，容易推知时间复杂度为O(logN)。
    long count = 0;
    long temp=n/5;
    while (temp!=0) {
        count+=temp;
        temp/=5;
    }
    return count;
}


int main()
{
    int a=5;
    long result = trailingZeros(a);
 
    printf("阶乘 %d 中0的个数: %ld ",a,result);
 
    printf("\n");
    return 0;
}

结果：

阶乘 50 中0的个数: 12

---

上一篇：Lintcode-1:A + B 问题
下一篇：Lintcode-3:统计数字