[LeetCode] 172. Factorial Trailing Zeroes

Posted on | In

Problem

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

Example 1:

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

Example 2:

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

Note: Your solution should be in logarithmic time complexity.

Explanation

  1. All trailing zeros are come from evenNum x 5, we have more evenNum than 5, so only count factor 5. For example:

    1
    2
    3
    4
    5
    6
    7
     4! = 1x2x3x4 = 24, we haven’t encountered any 5 yet, so we don’t have any trailing zero.

 5! = 1x2x3x4x5 = 120, we have one trailing zero. either 2×5, or 4×5 can contribute to that zero.

 9! = 362880, we only encountered 5 once, so 1 trailing zero as expected.

 10! = 3628800, 2 trailing zeros, since we have two numbers that have factor 5, one is 5 and the other is 10 (2×5)

  2. What about 100! then?

    100/5 = 20, we have 20 numbers have factor 5: 5, 10, 15, 20, 25, …, 95, 100.

    Is the number of trailing zero 20? No, it’s 24, why?

    Within that 20 numbers, we have 4 of them: 25 (5×5), 50 (2x5x5), 75 (3x5x5), 100 (4x5x5) that have an extra factor of 5.

    So, for a given number n, we are looking how many numbers <=n have factor 5, 5×5, 5x5x5, …

    Summing those numbers up we got the answer.

  3. For example 1000! has 249 trailing zeros:

    1
    2
    3
    4
    5
    6
    7
    8
    9
     1000/5 = 200

 1000/25 = 40

 1000/125 = 8

 1000/625 = 1

 200 + 40 + 8 + 1 = 249

    Alternatively, we can do the following:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
     1000/5 = 200

 200/5 = 40

 40/5 = 8

 8/5 = 1

 1/5 = 0

 200 + 40 + 8 + 1 + 0 = 249

Solution

1
2
3
4
5
6
7
8
9
10
class Solution {
    public int trailingZeroes(int n) {
        int res = 0;
        while (n >= 5) {
            res += n / 5;
            n = n / 5;
        }
        return res;
    }
}