算法:2.尾部的零

https://www.lintcode.com/problem/trailing-zeros/description

描述

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

样例

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

挑战

O(logN)的时间复杂度

思路

第一反应是尾部是0的数都能被5,10整除。假设阶乘的结果是N,那么N结尾的0的个数就是N能整除10的次数加上N能整除5的次数。

代码

第一个实现:

第二版的实现:

1public static long trailingZeros(long n) {

2    long count = ;

3    for(long i=5; i

4        long d = i;

5        while(d%5==) {

6            count++;

7            d /= 5;

8        }

9    }

10    return count;

11}

实际上0都是由5跟某个偶数相乘产生的,比如当n=5时,5!=120,最后的0就是2x5产生的。一个数字能产生多少0是看它是5的多少次方,比如5,10,15都只能产生1一个0,25则能产生2个0(4x25=100),125是3个(8x125=1000),依次类推。

上面的代码虽然减少了一个求余的循环,但是时间复杂度依然是O(n*logn),实际上之前对10求余的计算最后都落到了对5的求余中,计算量是没有减少的,反而是略有增加。

第三版实现:

这个算法已经达成了挑战目标O(logN)的时间复杂度。上面已经理解了0是由5产生的,而且一个数是5的几次方就产生几个0。那么第三版的计算也就好理解了。第一次除以5就将那些个位数是0,5的数字计算出来了,这些数每个数都贡献了1个0. 第二次就计算出了有多少个能贡献2个0的,依次类推。

小结

看似简单,但是要通过却不容易,使用求余几乎一定是执行超时。

最后除法是比乘法更耗时的运算,那么能不能将除法替换成乘法或别的运算呢?

......似乎是不能。

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20180713G1RA2500?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 yunjia_community@tencent.com 删除。

扫码关注云+社区

领取腾讯云代金券