Trailing Zeros in Factorial | InterviewBit | LeetCode | Solution Explained

I explain the solution to the problem Trailing Zeros in Factorial using simple observations and logic. Problem Link.

0. Trailing Zeros in Factorial: Problem Discussion

0.0. IO Format

• input:
  • an integer, n
• output:
  • an integer, which is the number of zeros in n!
• constraints:
  • 1 <= n <= 10⁴

0.1. Examples

• n = 2 -> 2! = 4 -> 0 trailing zeros
• n = 5 -> 5! = 120 -> 1 trailing zero
• and so on.

1. Trailing Zeros in Factorial: First Thoughts

The first instinct is to do as the question says. We know how to calculate factorial of a number in O(N) time and space each, so this solution shouldn’t be too hard?

There is one issue though. When it comes to factorials, the number grows fast. Even faster than exponentials – which is saying something. This means that by the time we reach 10⁴, we would have too many zeros. Yes, even for python3.

This means that we need to find an approach that does not calculate factorials, but just the number of zeros in a factorial.

2. Trailing Zeros in Factorial: Observations & Logic

2.0. Intuitions

The first thing to notice is that 10! does not have 1 zero for one 10 that is obviously present.

10! is 10.9.8….5….2.1.

Notice something? There’s a 5 and 2 also present, making the answer for 10 2, since we have one zero for 10 and the other for 5*2. The question itself hints at this with the 5! example, giving us 1 as the answer.

2.1. 5s and 2s

Now that we know we can form zeros with 5s and 2s, the next question is how many 5s and 2s can we get, apart from 10s?

In 20!, we have 10 and 20, but also 2,4,6,8,12,14,16,18 (we can extract at least one two from each) and then 5,15 (we can extract at least 1 five from each).

One thing that is very evident is that the number of 5s we can extract is much lower than the number of 2s that we can extract. In other words, 5 forms a bottleneck, so we can just count the number of multiples of 5s to get the answer!

Note how 20/5 = 4, which also happens to be the actual answer for n = 20!

2.2. Hidden in Plain Sight

It may seem tempting to assume n // 5 is the final answer. However, we haven’t really considered the cases where there can be multiple 5s hidden inside the number. Take for example, n = 30.

Online calculator can show that the number of 0s in 30 is 7. However, our logic will print 30/5 = 6. Where in the world did the extra 1 come from?

The big point is that there is a number, 25, in the 30! numbers list that contributes 2 to the final result – it has 2 multiples of 5 hidden inside of it.

This means that we:

• only care about multiples of 5
• of those multiples, we see how many 5s we can extract

And this brings us to the implementation.

3. Trailing Zeros in Factorial: Optimized Implementation

3.0. Code

int Solution::trailingZeroes(int A) {
    int count = 0;
    for (int i = 0; i < A+1; i += 5) {
        int x = i;
        while ((x % 5 == 0) && (x > 0)) {
            x /= 5;
            count++;
        }
    }
    return count;
}

class Solution:
    def trailingZeroes(self, A):
        count = 0
        
        for i in range(0, A+1, 5):
            while i % 5 == 0 and i:
                i //= 5
                count += 1
                
        return count

3.1. Complexity Analysis

• Time: O(N), to iterate over all the N values from 1 to 10^4. Note that O(N/5) = O(N)
• Space: O(1), since we do not store anything more than some counters.

Tanishq Chaudhary

Producing high-quality intuitive explanations of interview problems. Currently covering LeetCode and InterviewBit.