Trailing Zeros

Trailing Zeros
CSES easy

Find the number of trailing zeros of \(n!\) (the number of zeros at the end of its decimal notation). For example, \(20! = 2432902008176640000\) has \(4\) trailing zeros.

Constraints:

  • \(1 \le n \le 10^9\)

Input:

  • One line: integer \(n\).

Output:

  • One integer — the number of trailing zeros of \(n!\).

Example:

Input:

20

Output:

4
Solution

\(n!\) is far too large to compute, so we count its zeros in a different way.

Every trailing zero comes from a factor \(10 = 2 \cdot 5\). The product \(1 \cdot 2 \cdot \ldots \cdot n\) contains many more factors \(2\) than factors \(5\), so the number of trailing zeros equals the number of factors \(5\) in \(n!\).

We count the factors \(5\):

  • \(\lfloor n / 5 \rfloor\) numbers from \(1\) to \(n\) are divisible by \(5\); each gives one factor \(5\);
  • \(\lfloor n / 25 \rfloor\) of them are divisible by \(25\); each gives one more factor \(5\);
  • \(\lfloor n / 125 \rfloor\) of them give a third factor \(5\), and so on.

So the answer is \(\lfloor n / 5 \rfloor + \lfloor n / 25 \rfloor + \lfloor n / 125 \rfloor + \ldots\), and we stop when the power of \(5\) becomes larger than \(n\).

For \(n = 20\): \(\lfloor 20 / 5 \rfloor = 4\) and \(\lfloor 20 / 25 \rfloor = 0\), so the answer is \(4\).

#include <iostream>
using namespace std;

int main() {
    long long n;
    cin >> n;

    long long zeros = 0;
    // n / 5 numbers are divisible by 5, n / 25 by 25, and so on
    for (long long power = 5; power <= n; power *= 5) {
        zeros += n / power;
    }

    cout << zeros << "\n";
}