Trailing Zeros in Factorial

Given a non-negative integer n, compute the number of trailing zeros in n! (n factorial). The trailing zeros are produced by the factors 10 in the factorial, and since 10 is the product of 2 and 5, and factorials provide an abundance of factor 2, the number of zeros is determined by the number of times 5 divides n!. Formally, the answer can be computed by the formula:

\(\lfloor \frac{n}{5} \rfloor + \lfloor \frac{n}{5^2} \rfloor + \lfloor \frac{n}{5^3} \rfloor + \cdots \)

Your task is to calculate this sum efficiently even for large values of n (up to 10⁹).

inputFormat

The input consists of a single integer n (0 ≤ n ≤ 10⁹), read from stdin.

outputFormat

Output a single integer representing the number of trailing zeros in n!. The result should be written to stdout.

1

0