Factorial Trailing Zeroes [Microsoft Python Interview Question]

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 $n$ factorial as follows:

$n! = n * (n-1) * (n-2) * ..... 2 * 1$.

Now that you know the factorial formula, let's write a function that returns the number of trailing zeroes in n!.

For example, for $5!$, we'd return 1, because $5! = 5 * 4 * 3 * 2 * 1 = 120$ and 120 has exactly 1 trailing zero.

For $10!$, which evaluates to $3628800$ 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?

Trailing Zeroes Formula

When does a zero occur at the end of a factorial?

When there's a 5.

For example, in $5! = 5 * 4 * 3 * 2 * 1 = 120$ there's 1 trailing zero.

Notice in $4! = 4 * 3 * 2 * 1 = 24$ there's no trailing zero.

The zero in $5!$ came from multiplying 5 by 2.

Let's look at $10! = 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1$

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!

.

.

.

.

.

.

.

.

.

.

.

.

.

SIKE.

.

.

.

.

.

.

.

.

.

.

.

.

DID YOU RUN THE CODE?

.

.

.

.

.

.

.

.

.

.

We only passed half the test cases!

Let's take a loot at test case #3, $30!$, where we'd expect 6 trailing zeros, right?

But surprisingly, there are 7 trailing zeroes in $30! = 265252859812191058636308480000000$.

So, why the off-by-one error?

Because we forgot that 25 contributes not 1, but TWO 5s ($25 = 5 * 5$).

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 $125!$ – what do we do there?

Do you notice that $125 = 5 ^ {3}$.

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 $n$.

Here's that final code: