172. Factorial Trailing Zeroes (E)

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

Example 1:

Input: 3
Output: 0
Explanation: 3! = 6, no trailing zero.

Example 2:

Input: 5
Output: 1
Explanation: 5! = 120, one trailing zero.

Note: Your solution should be in logarithmic time complexity.

题意

统计给定数n阶乘后结尾0的个数。

思路

问题可以转化为 求因数10的个数 → 求因数5和2的个数 → 求因数5的个数(因为2的个数远远大于5的个数)。依照下面步骤进行操作：统计1-n范围内5的倍数的个数、25的倍数的个数、125的倍数的个数……

代码实现

class Solution {
    public int trailingZeroes(int n) {
        int count = 0;
        while (n  != 0) {
            count += n / 5;
            n /= 5;
        }
        return count;
    }
}