algorithm - the number of trailing zeros in a factorial of a given number - Ruby

Question

Having a little trouble trying calculate the number of trailing zeros in a factorial of a given number. This is one of the challenges from Codewars- can't get mine to pass.

zeros(12) = 2       #=> 1 * 2 * 3 .. 12 = 479001600 

I think I'm on the wrong path here and there is probably a more elegant ruby way. This is what I have down so far.

def zeros(n) 
    x = (1..n).reduce(:*).to_s.scan(/[^0]/)
    return 0 if x == [] 
    return x[-1].length if x != [] 
end

Answer 1

This is more of a math question. And you're right, you are off on a wrong path. (I mean the path you are on is going to lead to a very inefficient solution)

Try to reduce the problem mathematically first. (BTW you are shooting for a log N order algorithm.)

In my answer I will try to skip a few steps, because it seems like a homework question.

The number of trailing zeros is going to be equal to the total power of 5s in the multiplication of the series.

the numbers between 1 and n will have n/5, n/25, n/125 numbers which are multiples of 5s, 25s, 125s respectively... and so on.

Try to take these hints and come up with an algorithm to count how many powers of 10 will be crammed in to that factorial.

Spoilers Ahead

I've decided to explain in detail below so if you want to try and solve it yourself then stop reading, try to think about it and then come back here.

Here is a step by step reduction of the problem

1.

The number of trailing zeros in a number is equivalent to the power of 10 in the factor of that number

e.g.

• 40 = 4 * 10^1 and it has 1 trailing zero
• 12 = 3 * 4 * 10^0 so it has 0 trailing zeros
• 1500 = 3 * 5 * 10^2 so it has 2 trailing zeros

2.

The number power of 10 in the factors is the same as the minimum of the power of 2 and power of 5 in the factors

e.g.

• 50 = 2^1 * 5^2 so the minimum power is 1
• 300 = 3^1 * 2^2 * 5^2 so the minimum is 2 (we are only concerned with the minimum of the powers of 2 and 5, so ignore powers of 3 and all other prime factors)

3.

In any factorial there will be many more powers of 2 than the powers of 5

e.g.

• 5! = 2^3 * 3^1 * 5^1
• 10! = 2^8 * 3^4 * 5^2 * 7^1

As you can see the power of 2 is going to start increasing much faster so the power of 5 will be the minimum of the two.

Hence all we need to do is count the power of 5 in the factorial.

4.

Now lets focus on the power of 5 in any n!

• 4! ~ 5^0
• 5! ~ 5^1 (up to 9!)
• 10! ~ 5^2 (up to 14!)
• 15! ~ 5^3 (up to `19!)
• 20! ~ 5^4 (up to 24!)
• 25! ~ 5^6 (notice the jump from 5^4 to 5^6 because the number 25 adds two powers of 5)

5.

The way I'd like to count the total power of five in a factorial is... count all the multiples of 5, they all add one power of 5. Then count all the multiples of 25, they all add an extra power of 5. Notice how 25 added two powers of 5, so I can put that as, one power because it's a multiple of 5 and one extra power because it's a multiple of 25. Then count all the multiple of 125 (5^3) in the factorial multiplication, they add another extra power of 5... and so on.

6.

So how'd you put that as an algorithm ?

lets say the number is n. So...

• pow1 = n/5 (rounded down to an integer)
• pow2 = n/25
• pow3 = n/125

and so on...

Now the total power pow = pow1 + pow2 + pow3 ...

7.

Now can you express that as a loop?