Factorials and Trailing Zeros

Here’s a seemingly impossible and odd query that I’ve been asked in a technical interview:

Question: “How many trailing zeros are there in 126! (factorial)”

At the time I was left stumped and made sure to find out the solution later - so here it is! It turns out there’s a simple solution that works for all numbers.

Answer: 

Firstly, as a quick reminder, a factorial is the product of an integer and the integers below it. For 126! it is: 126 * 125 * 124 * … 3 * 2 * 1

Which can be shown as: n * (n – 1) * (n – 1) * …

Now the solution. The simplest way has three steps, i.e. for number n:

1. Divide the number n by 5 and write down the quotient. Ignore remainders (if any).
2. Then divide the quotient by 5 again and again till you get a quotient less than 5.
3. Add up all the resultant quotients to get the number of zeros in n!

Therefore, for 126! We get to the answer via:

126 / 5 = 25 (Actually 25.2 but we ignore the fraction. Note that 125 / 5 gives us the whole number of 5 – this will be useful in a moment)

25 / 5 = 5

5 / 5 = 1

25 + 5 + 1 = 31 zeros in 126!

This pattern can be shown as:

[ ] indicates only whole numbers; neglect any fractional part in the division process. This pattern may make more sense when we note that 52 is 25 and 53 is 125. The formula technically goes on till infinity but fractions are considered as 0 so do not affect the final result.

For 126! This resulted in [25] + [5] + [1] = 31.

Why does this work? Well, here’s an explanation: We know that a number gets a zero at the end of it if the number has 10 as a factor, e.g. 10 is a factor of 20, 150, and 99990. Also, 5 * 2 = 10, so we need to account for all the products of 5 and 2. However, every other factor is even, so there are far more factors of 2 than 5 - As such, we have to count the number of factors divisible by 5. To phrase it differently, there are many more numbers that are multiples of 2 (2, 4, 6, 8, 10, 12, 14, ...) than are multiples of 5 (5, 10, 15, ...). If we were to take all the numbers with 5 as a factor, we'll have way more than enough even numbers to pair with them to get factors of 10 (and another trailing zero on the factorial). Finally, we need to consider numbers which are factors of 5 and count them again, e.g. 25 (which is 5 * 5 or 52), 125 (5 * 5 * 5 or 53), 625 (5 * 5 * 5 * 5 or 54) etc.

To conclude, here is 126! in full (feel free to count the trailing zeros):

23721732428800468856771473051394170805702085973808045661837377170052497697783313457227249544076486314839447086187187275319400401837013955325179315652376928996065123321190898603130880000000000000000000000000000000

The approximate value is: 2.37217324288E+211