Trailing Zeros

12 July 2021

Statement

( The original statement can be found here )
Your task is to calculate the number of trailing zeros in the factorial n!. For example, 20!=2432902008176640000 and it has 4 trailing zeros.

Input
The only input line has an integer n.

Output
Print the number of trailing zeros in n!.

Constraints
1 ≤ n ≤ 10^9
Time limit : 1.00s
Memory limit : 512MB


Example

Input :
20

Output :
4

Solution

How many trailing zeros does N! have? In other words, how many times can we divide N! by 10 until it's no longer divisible by 10.

One way of finding this out is by looking at the prime factorization of N!. If 10 divides N! then the prime factorization of 10 must be contained in the prime factorization of N! and since 10=2x5 then the question becomes how many pairs {2,5} are in N! prime factorization.

Since 2 is a much more common factor and the pair requires both numbers to be present the answer becomes the number of times 5 appears in N! prime factorization. Given that N! is the product of all positive integers less than or equal to N we can conclude that the answer is the number of times 5 comes up in the prime factorization of all integers belonging to the interval [1, N].

One might guess that the answer is N/5 since that's the number of multiples of 5 in the interval but this would be wrong since 25 has two 5's in its prime factorization and 125 has three and so on. To solve this problem we must take into account every multiple of every power of five less than N. So if N=50 the answer would be 50/5 + 50/25.

The following expression shows a generalization for any given N (where M is the largest integer such that 5^M ≤ N)

#include <bits/stdc++.h>
using namespace std;

int main() {
    long n, current = 5, answer = 0;
    cin >> n;
    while (current <= n) {
        answer += n / current;
        current *= 5;
    }
    cout << answer << endl;
    return 0;
}

This algorithm runs in time complexity of O(log_5(n)) and space complexity of O(1).