How To calculate Trailing Zeros in N factorail | count Number of trailing zero in N! CSES problem solution

 How To calculate Trailing Zeros in N factorail | count Number of trailing zero in N! CSES problem solution -

This problem is taken form CSES Introductory Problem set. Here You have to count number of trailing zero in N!.

Problem Statement-

Your task is to calculate the number of trailing zeros in the factorial  n!$n!$.

For example, 20!=2432902008176640000$20!=2432902008176640000$ and it has 4$4$ trailing zeros.

Input

The only input line has an integer n$n$.

Output

Print the number of trailing zeros in n!$n!$.

Constraints

• 1≤n≤109$1\le n\le {10}^9$
  

Example

Input:
20

Output:
4




Solution-

Recommended practice yourself Before jumping to solution.

Problem link-https://cses.fi/problemset/task/1618/

So here is A hidden logic behind solving this problem. Think Condition when zero comes as trailing zero when we multiply two numbers.

Zero comes at the end when a number multiplied by 10. So we have to find How many times 10 can be formed in N!.

since 10 is multiple is 2 and 5 so we can get 10 only when 2 and 5 are multiplied so it is better to find how many times we 5 occur in N!.

So For finding number of 5 in N! we have a formula.

Join me on Telegram-https://t.me/competitiveProgrammingDiscussion

Trailing 0s in n! = Count of 5s in prime factors of n!
                  = floor(n/5) + floor(n/25) + floor(n/125) + ....

So this is how we can calculate the number of trailing Zeros in N!.

Code Solution of this Problem-