Back to questions
Before, you work on this question, make sure you've solved the easier warmup problem Factorial Formula, where you need to write a function to compute factorial as follows:
.
Now that you know the factorial formula, let's write a function that returns the number of trailing zeroes in n!.
For example, for , we'd return 1, because and 120 has exactly 1 trailing zero.
For , which evaluates to we'd return 2, becuase there are two trailing zeroes.
We could use the iterative approach from the Factorial Formula Interview Question to first compute a factorial:
We can use this code as a helper function, as part of our bigger solution.
Now that we can get a factorial, it's time to start counting the trailing zeroes. Here's a snippet to do that where we repeatedly divide by 10 and make sure there is no remainder left after the division:
Putting these snippets together, here's the code we get:
This solution would make a Software Engineer happy – but we aren't Software Engineers! We are men and women of data.
Can we think of a smarter, more mathematical way to do this?
When does a zero occur at the end of a factorial?
When there's a 5.
For example, in there's 1 trailing zero.
Notice in there's no trailing zero.
The zero in came from multiplying 5 by 2.
Let's look at
Even without computing this total, we'd expected two trailing zeroes – one from the 5 multiplying by 2, and the other from the 10 multiplying any other number that's a factor of 2, like 4, 6, 8.
Starting to see a pattern? We don't care about 2s. We need to count the factors of 5.
We can floor division – the '//' operator, which chops off the remainder and returns a whole integer, to count the factors of 5.
Example: '13 // 5 = 2'.
So, our code looks something like this:
So simple, we're done, thanks for reading!
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
We only passed half the test cases!
Let's take a loot at test case #3, , where we'd expect 6 trailing zeros, right?
But surprisingly, there are 7 trailing zeroes in .
So, why the off-by-one error?
Because we forgot that 25 contributes not 1, but TWO 5s ().
So not only do we need to count 5's, we need to count 25's since they give us an extra 5 to deal with.
So the code looks like this now:
But what about – what do we do there?
Do you notice that .
To generalize this, we can divide by 5, 25, 125, and keep going up by powers of 5 while they are still less than our input number .
Here's that final code:
Python