Counting Factorial Trailing Zeroes

This challenge asks you to find the number of trailing zeroes in the factorial of a given non-negative integer. Trailing zeroes in factorials are important in various mathematical and computational contexts, such as in problems involving large number representations and combinatorial analysis.

Problem Description

Given a non-negative integer n, your task is to calculate the number of trailing zeroes in n! (n factorial).

• Factorial Definition: For a non-negative integer n, n! is the product of all positive integers less than or equal to n.

  • 0! = 1
  • 1! = 1
  • 2! = 2 * 1 = 2
  • 3! = 3 * 2 * 1 = 6
  • n! = n * (n-1) * ... * 2 * 1

• Trailing Zeroes: Trailing zeroes are the zeroes that appear at the end of a number. For example, 1200 has two trailing zeroes.

• Goal: Determine how many zeroes are at the end of the decimal representation of n!.

• Expected Behavior: The function should accept a non-negative integer n and return a non-negative integer representing the count of trailing zeroes.

• Edge Cases:

  • n = 0: 0! = 1, which has zero trailing zeroes.
  • Small values of n where the factorial is easily calculable by hand to verify results.

Examples

Example 1:

Input: n = 3
Output: 0
Explanation: 3! = 3 * 2 * 1 = 6. The number 6 has no trailing zeroes.

Example 2:

Input: n = 5
Output: 1
Explanation: 5! = 5 * 4 * 3 * 2 * 1 = 120. The number 120 has one trailing zero.

Example 3:

Input: n = 10
Output: 2
Explanation: 10! = 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 = 3,628,800. The number 3,628,800 has two trailing zeroes.

Example 4:

Input: n = 0
Output: 0
Explanation: 0! = 1. The number 1 has no trailing zeroes.

Constraints

• 0 <= n <= 10^4 (or a sufficiently large upper bound that prevents direct factorial calculation from overflowing standard integer types in most languages).
• The input n will be a non-negative integer.
• Your solution should aim for an efficient time complexity, avoiding the direct computation of n!.

Notes

• Trailing zeroes in a number are created by factors of 10.
• A factor of 10 is the product of a factor of 2 and a factor of 5 (10 = 2 * 5).
• When calculating n!, you will have many more factors of 2 than factors of 5. Therefore, the number of trailing zeroes is limited by the number of factors of 5 in the prime factorization of n!.
• Consider how to count the factors of 5 efficiently from the numbers 1 through n. For instance, numbers like 5, 10, 15, 20 contribute one factor of 5, while numbers like 25 (55), 50 (25*5) contribute multiple factors of 5.
• Think about multiples of 5, multiples of 25, multiples of 125, and so on.