#172
Factorial Trailing Zeroes
Medium Counting factors
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Return how many zeros n! ends with.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: how many zeros are at the end of n!?
Why this works: each zero is a 10 = 2 × 5, and 2s are always plentiful, so count the 5s. Numbers like 25 give two 5s.
Example: n = 30
30 / 5 = 6 (5,10,15,20,25,30)30 / 25 = 1 (the extra 5 in 25)total 7 zeros
✦Hints open one at a time
Each trailing zero comes from a factor 10 = 2 × 5.
There are always more 2s than 5s, so count the 5s.
25 contributes two 5s, 125 three… count n/5 + n/25 + n/125 + …
↗Approach
Keep dividing n by 5 and add each quotient. That counts multiples of 5, then extra 5s from multiples of 25, and so on.
</>Solution (Java)
class Solution {
public int trailingZeroes(int n) {
int count = 0;
while (n > 0) {
n /= 5;
count += n; // multiples of 5, then 25, then 125...
}
return count;
}
}!Common mistake
Computing n! directly — it overflows almost immediately.
Complexity
- Time: O(log5 n).
- Space: O(1).
