算法：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的，依次类推。

小结

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

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

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