尾部的零

发表于 分类于 阅读次数： 本文字数： 425 阅读时长 ≈ 2 分钟

前言

LintCode-尾部的零
描述
设计一个算法，计算出n阶乘中尾部零的个数

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

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

思路

这么简单, 递归阶乘, 转字符串, 从后往前遍历

上面的方法当然是超时了.
网上也已经有很多解题思路, 自己再总结一下。
这个问题可以换个问法, n!=K*10^M, 求M。
在样例中, n! = K * 10^M = 11! = 399168 * 10^2。
也就是说, 尾部有多少个零, 那么就是K乘以10的多少次方。

再转化一下

1
2
3
4
5
6
7
11! = 1 * 2 * 3 *    4    * 5 *    6    * 7 *      8      *    9    *   10    * 11
11! = 1 * 2 * 3 * (2 * 2) * 5 * (2 * 3) * 7 * (2 * 2 * 2) * (3 * 3) * (2 * 5) * 11
11! = 1 * 7 * 11 * 3^4 * 2^8 * 5^2
11! = (1 * 7 * 11 * 3^4 * 2^6) * 2^2 * 5^2
11! = (1 * 7 * 11 * 3^4 * 2^6) * (2 * 5)^2
11! = (399168) * 10^2
n!  = K * 10^M

可以看到解题方法就是找出因式分解后, 里面有多少个 2*5的组合。
从上面可以看出, 2的数量一定是比5多的。
所以, 因式分解后有多少个5, 尾部就有多少个零。

再转化一下, 能被5整除的因子必然是5的倍数, 也就是说, 找出n之前有多少个5的倍数(这是不正确的)。
还需要考虑到25, 125等数字。

n 因子是5的倍数 计算方法 多少个零
11 5, 10 11 / 5 = 2 2
26 5, 10, 15, 20, 25 26 / 5 + 26 / 25 = 6 6
1000 5, 10, 15, …. 995, 1000 1000 / 5 + 1000 / 25 + 1000 / 125 …. = 249 249

代码

1
2
3
4
5
6
7
8
public long trailingZeros(long n) {
    long count = 0;
    while (n != 0) { 
        count += n / 5;
        n /= 5;
    }
    return count;
}