Factorial Trailing Zeroes

https://leetcode.com/problems/factorial-trailing-zeroes/description/

Given an integern, return the number of trailing zeroes inn!.

Note:Your solution should be in logarithmic time complexity.

Thoughts

每个0都是由一个2和一个5相乘得到的.

所以要知道的是N!能有多少个2和5.

由于2的数目比5多很多, 最终我们只要关心有多少个5.

比如10!有两个5, 分别来自5和5 * 2.

可以看到N / 5 表示了N!中有多少个5的倍数.

10 / 5得2, 因此10!有两个数分别为5 * 1和5 * 2会是5的倍数.

5的倍数只关心了一个5, 我们还要对25 (5 * 5, 两个5), 125 (5 * 5 * 5三个5), ...等等重复此过程, 也就是n = n/5依然>0, 说明当前n至少是5 * 5.

虽然5的倍数时考虑了25, 125, 但在5的倍数时只相当于"消耗"了它们中的第一个5, 还剩下1个和2个有待"消耗". 所以对25和125等数有几个倍数时不用担心重复.

Code

class Solution {
    public int trailingZeroes(int n) {
        int res = 0;
        while (n > 0) {
            res += n / 5;
            n = n / 5;
        }

        return res;
    }
}

Analysis

时间复杂度O(lgN), 5为底.