Given an integer n, return the number of trailing zeroes in n!.
Note that n! = n * (n - 1) * (n - 2) * ... * 3 * 2 * 1.
Example 1:
Input: n = 3 Output: 0 Explanation: 3! = 6, no trailing zero.
Example 2:
Input: n = 5 Output: 1 Explanation: 5! = 120, one trailing zero.
Example 3:
Input: n = 0 Output: 0
Constraints:
0 <= n <= 104
Follow up: Could you write a solution that works in logarithmic time complexity?
Problem Overview: Given an integer n, return the number of trailing zeroes in n! (n factorial). Trailing zeroes come from factors of 10, which are produced by pairs of 2 × 5 in the factorial multiplication.
Approach 1: Iterative Counting (O(n) time, O(1) space)
One straightforward way is to scan every number from 1 to n and count how many times 5 appears as a factor. Each time you encounter a multiple of 5, divide it repeatedly by 5 and add to the count. For example, 25 contributes two factors of 5, while 125 contributes three. The accumulated count equals the number of trailing zeroes in n!. This approach directly reflects the underlying math but iterates through every number, giving it O(n) time complexity and O(1) extra space.
Approach 2: Counting Factors of 5 (O(log n) time, O(1) space)
The key observation: trailing zeroes only depend on how many times 5 appears in the prime factorization of numbers from 1 to n. Factors of 2 are abundant, so 5 is the limiting factor. Instead of checking every number, repeatedly divide n by 5 and accumulate the quotients: n/5 + n/25 + n/125 + .... Each division counts multiples of higher powers of 5 that contribute additional factors. The loop runs only log₅(n) times, making the algorithm extremely efficient. This technique is a classic number theory trick frequently used in math-based interview problems.
Recommended for interviews: Counting factors of 5 is the expected solution. It demonstrates that you recognize the relationship between trailing zeroes and prime factors of 10. Mentioning the naive iterative counting approach shows you understand the reasoning, but implementing the n/5 + n/25 + ... formula proves you can optimize using mathematical insight. Interviewers typically look for the O(log n) solution.
To determine the number of trailing zeroes in a factorial (n!), observe that trailing zeroes are produced by 10s in the factorization of n!. Each 10 is the product of a 2 and a 5. In most factorial numbers, there are more factors of 2 than 5. Therefore, the number of trailing zeroes is determined by the number of times 5 is a factor. We count the number of multiples of 5 in the numbers from 1 to n (because each contributes at least one factor of 5). Then, we count the multiples of 25, 125, 625, etc., as these contribute an extra factor of 5 each time. Continue this counting until the power of 5 exceeds n.
The function trailingZeroes calculates the number of trailing zeroes in the factorial of a given number n. It repeatedly divides n by 5, adding the quotient to count, which represents the number of trailing zeroes.
C++
Java
Python
C#
JavaScript
Time Complexity: O(log5 n)
Space Complexity: O(1)
In this approach, we directly count the number of trailing zeroes by iterating over all the numbers up to n, checking if each is divisible by 5. If so, we increment a counter to track the factors of 5. This approach isn't as efficient as counting the most significant power of 5 due to potentially higher iteration counts.
This C implementation iterates over numbers from 1 to n. For each number, if it is divisible by 5, it divides it further, counting each division as a factor of 5.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n log5 n)
Space Complexity: O(1)
| Approach | Complexity |
|---|---|
| Counting Factors of 5 | Time Complexity: O(log5 n) |
| Iterative Counting | Time Complexity: O(n log5 n) |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative Counting of Factors | O(n) | O(1) | When explaining the reasoning behind trailing zeroes or building intuition about factor counting |
| Counting Factors of 5 (Division Method) | O(log n) | O(1) | Best choice for interviews and production code; avoids scanning every number |
Number of Trailing Zeros in a Factorial • Neso Academy • 38,437 views views
Watch 9 more video solutions →Practice Factorial Trailing Zeroes with our built-in code editor and test cases.
Practice on FleetCode