Medium–hard · the insight is arithmetic

Trailing Zeros

The input is too large to compute. That's not a bug in the problem — it's the problem telling you the answer isn't in the computation.

At a glanceTrailing zeros come from factors of 5, so the answer is n/5 + n/25 + n/125 + … — never compute n!, which is astronomically large for n up to 10⁹.

Problem

Input: One integer n (1 ≤ n ≤ 1,000,000,000).

Output: How many trailing zeros n! has, where n! = 1 × 2 × … × n.

Samples:

Input	Output
`5`	`1`
`10`	`2`
`25`	`6`

10! = 3628800 → two zeros. 25! = 15511210043330985984000000 → six. Note that 25/5 is only 5 — the sixth zero comes from 25 contributing two factors of 5.

Your solution

main.cpp — your solution

Custom input for "Run my input"

Judging runs in your browser against hidden tests. A runaway loop is cut off after 3 seconds — still, make sure every loop has an exit. Your code is saved in this browser as you type.

Stuck? Hints

Hint 1 — A trailing zero is a factor of 10

Every zero at the end means the number is divisible by another 10, and 10 = 2 × 5. So the question becomes: how many pairs of (2, 5) are hiding in n!? Since even numbers are far more common than multiples of 5, the number of 5s is the limiting factor — so just count the 5s.

Hint 2 — Not n/5 — that's the trap

n / 5 counts multiples of 5, but 25 contributes two 5s, 125 contributes three, and so on. Add n / 25, then n / 125, and keep going. The loop is beautifully short: while (n > 0) { n /= 5; zeros += n; } — divide n itself and accumulate.

Hint 3 — Why you must not loop from 1 to n

Multiplying 1 × 2 × … × 1,000,000,000 is 10⁹ iterations, and the number itself would overflow every integer type long before that. Even if it fit, the tab would freeze. When the input range makes brute force impossible, that is a hint: the intended solution is O(log n) or O(1).

Solution (try it first!)

#include <iostream>
using namespace std;

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

This is the last problem in the chain, and it's a fitting one: no arrays, no loops over the input, no recursion — just one observation that replaces a billion multiplications with a dozen divisions. That's the difference between a programmer and someone who can program: the second one sees that the question was never about the factorial. Go back to the list and see how many you can now do without hints.

Deep dive

Why this works

Every trailing zero is a factor of 10, and 10 = 2 × 5. Even numbers vastly outnumber multiples of 5, so the 5s are the bottleneck — count those.

The cost

O(log_5 n): twelve divisions for a billion. Multiplying from 1 to n would be 10^9 multiplications, and the number would overflow long before that.

Where it goes wrong

Computing only n / 5 misses the extra 5 contributed by 25 and the extra two by 125 — off by one already at n = 25.
Trying to actually compute n!: at a billion it overflows every integer type and freezes the tab. An input range that rules out brute force *is* the hint.

Next step

That's the end of the chain. Look back at the first problem and see how far you've come.

Two things to remember

Trailing zeros = pairs of 2×5, and 5 is the scarce side.
n / 5 isn't enough — you also need n / 25, n / 125…

🐞 This version fails — open it and try

Only n / 5 — misses the extra fives from 25, 125, 625…

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    long long zeros = n / 5;
    cout << zeros << endl;
    return 0;
}