Trailing Zeroes in Factorial

Given a non-negative integer n, compute the number of trailing zeroes in n! (n factorial). The trailing zeroes in n! are created by the factors 10, which is a product of 2 and 5. Since there are usually more factors of 2 than 5, the count of trailing zeroes is determined by the number of times 5 is a factor in n!. Mathematically, this can be expressed as:

$$ Z(n) = \left\lfloor \frac{n}{5} \right\rfloor + \left\lfloor \frac{n}{5^2} \right\rfloor + \left\lfloor \frac{n}{5^3} \right\rfloor + \cdots $$

Your task is to implement an efficient algorithm to compute Z(n) for a given n.

inputFormat

The input consists of a single line containing a non-negative integer n (0 \(\leq\) n \(\leq\) 10⁹).

outputFormat

Output a single integer which is the number of trailing zeroes in n!.

10

2