Factorial Trailing Zeroes
Medium· number theory
Problem
Return the number of trailing zeros in n factorial. Computing n! directly is infeasible for large n, so find a counting argument instead.
Examples
Input: n = 5
Output: 1
5! = 120.
Input: n = 25
Output: 6
Constraints
- • 0 <= n <= 10^4
Hints & approach
Hint 1
Each trailing zero comes from a factor of 10 = 2 × 5.
Hint 2
Factors of 2 are plentiful; count the factors of 5.
Hint 3
Multiples of 25 contribute an extra 5, multiples of 125 another, and so on.
Approachtry the hints first
Trailing zeros equal the number of 10s in n!, which is limited by the number of factors of 5. There are ⌊n/5⌋ multiples of 5, ⌊n/25⌋ of them contribute a second 5, ⌊n/125⌋ a third, and so on (Legendre's formula). Repeatedly divide n by 5 and add the quotient until it reaches 0.
Time O(log n) · Space O(1)