adamcrussell

n! has how many trailing zeroes?

Perl Weekly Challenge 072 asks 

You are given a positive integer $N (<= 10). Write a script to print number of trailing zeroes in $N!.

Note that the number of zeroes is equivalent to the number of factors of 10 in n!. For example, 4! = 4 * 3 * 2 * 1 which has none. 6! = 6 * 5 * 4 * 3 * 2 * 1 = 6 * 4 * 3 *1 * (5 * 2) has one. 10! = 10 * 9 * 8 * 7 * 6 * 4 * 3 * 1 * (5 * 2) has two.

In this case, for n <= 10, we can can these cases directly.

sub count_10s{
   my($n) = @_;
   return 2 if $n == 10;
   return 1 if $n >=5 && $n < 10;
   return 0 if $n < 5;
}
 

If we wanted to solve this for the general case we would have to follow an algorithm that would look like this (pseudo code)

Function count 10s   

    Pass In: n, a whole number   

    Doing: For each term of n! = 1 * 2 * 3 * ... * n perform a prime factorization.
                Save all prime factors for all terms to an array. Count each pair of
               (2,5). This is the number of factors of 10 in n!

    Pass Out: the number of factors of 10 in n! 

Endfunction 

Comments for this post were locked by the author