Zeros at the End of a Factorial
EasyMath & Geometry
Problem
A calculator prints n! = 1 · 2 · ... · n in full. Without computing the factorial, return how many zeros it ends with.
By convention 0! = 1.
Example 1
- Input:
- n = 5
- Output:
- 1
5! = 120 ends with one zero.
Example 2
- Input:
- n = 26
- Output:
- 6
Multiples of 5 up to 26 give five factors of 5, and 25 contributes a sixth.
Example 3
- Input:
- n = 4
- Output:
- 0
4! = 24.
Constraints
- 0 ≤ n ≤ 10^15
Hint
Show the first hint
A trailing zero is a factor 10 = 2 · 5. Which of the two is scarcer in n!?
Walkthrough
How to approach it
01Clarify before coding
- Is 0! = 1? Yes, so n = 0 gives 0 zeros.
- n can reach 10^15: computing the factorial is impossible, so the answer must come from counting factors.
- Do we count only the trailing zeros, not zeros in the middle? Yes, only the ones at the end.
02Brute force
Compute n! with big integers and count the zeros at the end, or for each k ≤ n count how many times 5 divides it.
Cost: The factorial has about n log n digits; even the per-k counting is O(n), i.e. 10^15 steps.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.