172. Factorial Trailing Zeroes

LeetCode Math

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$ ，返回 $n!$ 结果尾数中零的数量。如果尾数中要有0，需要有5、2因数；又因为2的数量永远是足够的。所以尾数中零的数量等于 $n!$ 中5的数量。

例如数字2147483647，因式分解展开：

$\small \begin{align*}2147483647!=2 \times 3 \times ...\times 5 ... \times 10 ... 15\times ... *\times 25 ... \times 50 ... \times 125 ... \times 250...\\ =2 \times 3 \times ...\times 5 ... \times (5^1\times 2)...(5^1\times 3)...*(5^2*1)...*(5^2\times 2)...*(5^3 \times 1)...*(5^3 \times 2)... \end{align*}$

只要计数5的数量：5的倍数提供了一个5，25的倍数提供了2个5，也就是多提供了一个5。所以5的数量等于： $$ n/5 + n/25 + n/125 + n/625 + n/3125+...$$

// 递归形式
public int trailingZeroes(int n) {
    return n == 0 ? 0 : n / 5 + trailingZeroes(n / 5); 
}
// 迭代形式
public int trailingZeroes(int n) {
    if (n < 5) return 0;
    int count = 0;
    while (n > 4) {
        n /= 5;
        count += n;
    }
    return count;
}