Trailing Zeros
Count how many zeros appear at the end of n! without computing the factorial itself.
Problem Summary
Original task summary for this archive page. The official CSES statement is linked in the header instead of being mirrored here.
Determine how many zeros the decimal representation of \(n!\) ends with, without ever constructing the factorial explicitly.
Editorial
The solution write-up is rendered from the LaTeX source, with equations kept live through MathJax.
A trailing zero comes from a factor of \(10\), which is \(2 \times 5\).
In \(n!\), factors of \(2\) are much more common than factors of \(5\), so the answer is exactly the number of times \(5\) appears in the prime factorization of \(n!\).
Count those \(5\)-factors in layers:
every multiple of \(5\) contributes at least one factor of \(5\)
every multiple of \(25\) contributes one extra factor
every multiple of \(125\) contributes yet another extra factor
and so on
So the answer is \[ \left\lfloor \frac{n}{5} \right\rfloor + \left\lfloor \frac{n}{25} \right\rfloor + \left\lfloor \frac{n}{125} \right\rfloor + \cdots \] until the divisor exceeds \(n\).
Complexity Analysis
Time and memory costs for the approach used in the implementation below.
Time: \(O(\log_5 n)\)
Memory: \(O(1)\)
C++ Solution
The exact repository source used for this solution page.
#include <cstdint>
#include <iostream>
int main() {
std::int64_t n;
std::cin >> n;
std::int64_t answer = 0;
for (std::int64_t divisor = 5; divisor <= n; divisor *= 5) {
answer += n / divisor;
}
std::cout << answer << '\n';
return 0;
}
Notes / Pitfalls
Short reminders about edge cases, construction details, or common mistakes.
This is a counting problem, not a big-integer problem. Never try to build \(n!\) directly.
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.