Number of trailing zeros in n factorial

I was asked this question in my first job interview in the US. I was completely unprepared for this type of interview, and I did badly. But it’s a nice problem to think about and it’s easy to solve.

In case you don’t know, n factorial is the multiplication of all positive integers less than or equal to n. By convention, 0 factorial is taken as 1. The factorial is typically represented with “!”.

So:

0! = 1
1! = 1
2! = 2 1 = 2
3! = 3 2 1 = 6

And so on. You may have noted the following pattern: n! = n (n-1)! This leads to the following recursive function in the Scheme language (you can get Scheme system here)

(define (factorial n)
  (if (= n 0)
      1
      (* n (factorial (- n 1)))))

You can feed this to the Scheme system, and start getting numbers.

(factorial 0)  --> 1
(factorial 3)  --> 6
(factorial 32) --> 263130836933693530167218012160000000

So, we want to be able to compute that 32! has 7 trailing zeros, but we don’t want to have to compute 32!

The key observation is this: the number of zeros equals the number of times 10 is a factor in 32! (or n!). 10 = 2 5, and since 2 appears more often than 5 in n!, we can say that the number of trailing zeros is the same as the number of times 5 is a factor in n!

Now, how do we count the number of times 5 is a factor? We can begin by observing that 32! = 32 31 30 .. 25 .. 20 .. 15 .. 10 .. 5 .. 1 (the .. stand for omitted numbers). So, we can see 6 of the factors in 32! are multiples of 5. And we can compute this number simply by diving by 5: 32 / 5 = 6 (assuming we discard the decimal part). That’s a start.

Now, we also have 25 in there, and it has two factors of 5; we need to account for the extra five. So, there are 6 + 1 = 7 factors of 5 in 32!, and 7 trailing zeros, which you can verify above. Nice. We could have started the opposite way, counting the number of double fives first, multiplying them by 2, then adding the single fives. But if we did that, we would have  to throw away the 25 when progressing toward the single fives, and that would be more baggage to keep track of. This way, also, we count for the double five only once, because 25 had been counted once as a single five.

So, number of fives in 32! = 32 / 5 + 32 / 25 = 6 + 1 = 7

We can formulate an algorithm informally: Number of fives in n! = n / 5 + n / 25 + n / 125 ... (/ is assumed to be integer division ie. it discards decimals). Let’s give this function a name: fives-in-factorial(n). By the way, the ’...’ means and so on, but it would not make sense to go on forever, once one of the summands reaches 0.

Maybe you can see a pattern here: fives-in-factorial(n) = n / 5 + (n / 5) / 5 + (n / (5 * 5)) / 5 ...

This suggests a recursive definition:

fives-in-factorial(n) = n/5 + fives-in-factorial(n/5)

The base of the recursion is that for n < 5, there are no fives in n!, hence fives-in-factorial(n) = 0

Translated into code:

(define (fives-in-factorial n)
  (if (< n 5)
      0
      (+ (floor (/ n 5))
         (fives-in-factorial (/ n 5)))))

(In case you’re wondering about floor: given a number, it discards its decimal part). You can again introduce this code in a Scheme system and start getting some answers. We already know 32.

(factorial 32)           → 263130836933693530167218012160000000
(fives-in-factorial 32)  → 7

(factorial 6)            → 720
(fives-in-factorial 6)   → 1

(factorial 46)           → 5502622159812088949850305428800254892961651752960000000000
(fives-in-factorial 46)  → 10