Leetcode 题目解析之 Factorial Trailing Zeroes

Given an integer n, return the number of trailing zeroes in n!.

Note: Your solution should be in logarithmic time complexity.

结果转换成3进制，结尾有多少个连续的0？

在面试时，曾遇到这样的一道题：

30!结果转换成3进制，结尾有多少个连续的0？

第一次做的话，感觉没有思路，但是换个角度想，转换成3进制，那么十进制中的1~30，哪些因子相乘，才会贡献出三进制结尾的0呢？当然是：3的倍数。

3， 6， 9， 12， 15 ，18， 21， 24， 27， 30

那么，每一个因子贡献了多少个0呢？

贡献了1个0的因子

3 = 3 * 1
6 = 3 * 2
12 = 3 * 4
15 = 3 * 5
21 = 3 * 7
24 = 3 * 8
30 = 3 * 10

30/3+30/9+30/27所代表的，就是最终结果。

这是因为：30/3把所有贡献了0的因子都算了一次，9、18、27已经被算过一次了，但是9和18还有一个因子没有算，27中还有两个因子没有算。

30/9则计算了一次9、18、27，但是27中还有一个因子没有算。

30/27计算了一次27，至此，所有的因子都计算完毕。

在代码中，一定要注意溢出的问题，如下代码（我的第一个代码）就不能通过测试。因为在n很大时，比如Integer.MAX_VALUE，i *= 5溢出了，i一直是小于等于n，所以是死循环！

    public static int trailingZeroes2(int n) {
        int rt = 0;
        for (int i = 5; i <= n; i *= 5) {
            rt += n / i;
        }
        return rt;
    }

解决方法，把n定义成long型。注意i也要定义成long型，否则在n很大时，主要是i * 5 > Integer.MAX_VALUE后会出错。

    public int trailingZeroes(int n) {
        int rt = 0;
        long N = n;
        for (long i = 5; i <= N; i *= 5) {
            rt += N / i;
        }
        return rt;
    }