Factorial Trailing Zeroes

The factorial of a non-negative integer n, denoted by n!, is the product of all positive integers less than or equal to n. This problem asks you to determine the number of trailing zeroes in the factorial of a given integer. Trailing zeroes in a factorial are a result of factors of 10, which come from pairs of 2 and 5 in the prime factorization.

Problem Description

Given a non-negative integer n, calculate the number of trailing zeroes in n!. Trailing zeroes are formed by factors of 10. Since 10 = 2 * 5, and there are always more factors of 2 than 5 in a factorial, we only need to count the number of factors of 5.

What needs to be achieved: Write an algorithm that takes an integer n as input and returns the number of trailing zeroes in n!.

Key requirements: The algorithm should efficiently count the number of factors of 5 in the prime factorization of n!.

Expected behavior: The function should return an integer representing the number of trailing zeroes.

Edge cases to consider:

• n = 0: 0! = 1, which has 0 trailing zeroes.
• n = 1: 1! = 1, which has 0 trailing zeroes.
• Large values of n: The algorithm should be efficient enough to handle large inputs without causing overflow or excessive computation time.

Examples

Example 1:

Input: 5
Output: 1
Explanation: 5! = 5 * 4 * 3 * 2 * 1 = 120. There is one trailing zero.

Example 2:

Input: 10
Output: 2
Explanation: 10! = 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 = 3628800. There are two trailing zeroes.

Example 3:

Input: 0
Output: 0
Explanation: 0! = 1. There are no trailing zeroes.

Example 4:

Input: 30
Output: 7
Explanation: 30! has seven trailing zeroes. This is because there are 7 factors of 5 (5, 10, 15, 20, 25, 30).  25 contributes two factors of 5, but we only count it once.

Constraints

• 0 ≤ n ≤ 10⁹
• The input n will always be a non-negative integer.
• The algorithm should have a time complexity of O(log n) or better. A naive approach that calculates the factorial directly will likely exceed time limits for larger values of n.

Notes

The number of trailing zeroes in n! is determined by the number of times 5 appears as a factor in the numbers from 1 to n. You can efficiently calculate this by summing the number of multiples of 5, 25, 125, and so on, up to n. Consider how to avoid calculating the factorial itself. Think about how many numbers between 1 and n are divisible by 5, 25, 125, etc.