Factorial Trailing Zeroes
The key idea
A trailing zero comes from a factor of
10 = 2 x 5. In n! factors of 2 are far more common than factors of 5, so the count of trailing zeros equals the count of factor 5s. Count them by summing n//5 + n//25 + n//125 + ... until the divisor exceeds n.Problem
Given an integer n, return the number of trailing zeroes in n!.
Recall that n! = n x (n - 1) x (n - 2) x ... x 2 x 1 and by convention 0! = 1.
The follow-up asks for a solution that runs in logarithmic time.
Constraints
- 0 <= n <= 10^4
- Follow up: Could you write a solution that works in logarithmic time complexity?
Examples
Input: n = 3
Output: 0
Input: n = 5
Output: 1
Input: n = 0
Output: 0
Complexity
Time: O(log n) Space: O(1)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization
More Math / Number Theory problems
- Add BinaryEASY
- Excel Sheet Column TitleEASY
- Greatest Common Divisor of StringsEASY
- Integer to RomanMEDIUM
- Multiply StringsMEDIUM
- Palindrome NumberEASY
- Plus OneEASY
- Reverse IntegerMEDIUM
- Roman to IntegerEASY