Factorial Zero Count

Slug: factorial-zero-count

Difficulty: Easy

Id: 891233

Summary

Given an integer n, find the number of trailing zeros in the factorial of n. For example, for n = 5, the result is 2 because 5! = 120, which has two trailing zeros.

This problem involves basic arithmetic operations and factorial calculations. The key concept is understanding how to calculate the number of trailing zeros in a factorial.

Detailed Explanation

To solve this problem, we need to understand that trailing zeros are formed by pairs of factors of 2 and 5. This means we only need to count the factors of 5 because there will always be more factors of 2 than 5.

Here's a step-by-step breakdown of the solution:

1. Initialize a variable count to store the number of trailing zeros.
2. Iterate from 2 to n (inclusive). For each iteration:
   • If i is divisible by 5, increment count. This is because every time we encounter a factor of 5, we get a trailing zero.
   • If i is also divisible by 25, increment count again. This is because every time we encounter a factor of 25, we get an additional trailing zero (since there will be more factors of 2 to pair with the 5s).
   • Continue this process until i > n.
3. Return the value of count.

The time complexity for this solution is O(n), as we need to iterate from 2 to n. The space complexity is O(1), as we only use a constant amount of space.

Optimized Solutions

Java