An integer n is given, the task is to find the number of trailing zeros in n! .

Solution

First we need to see what produces trailing zeros. We assume that the integers are represented in base 10. A pair of 5 and 2 (which are the prime factors of 10) will produce a trailing zero in a sequence of integer multiplication. The number of trailing zeros will not decrease as once a trailing zero is generated in a product it cannot be removed by multiplying with some non zero integer. For factorial of n the multiplication series is: n\times (n-1)\times(n-2)\times \ldots \times 3 \times 2 \times 1 . We need to count number of pairs of 5 and 2 present as a factor of each integer in the series. Naturally there are at least equal number of factors 2 than 5, if not more. Therefore basically the number of times 5 occurs as a factor totally in the series, ie. the multiplicity of the prime factor 5 in the factorial represents the number of trailing zeros.

For example in the case of 25! , the factor 5 occurs 6 times totally in the series of multiplication 25 \times 24 \times \ldots \times 3 \times 2 \times 1. 5, , ie. the multiplicity of the factor 5 is 6. The integers 10, 15, 20 is divided by 5 once, and twice for 25.

Therefore now the problem decreases to count the number of times the factor 5 occurs in the given series of multiplication. Which can be found as below:

trailing zeros = \sum_{i=1}^{k} \left\lfloor n/5^i \right\rfloor = \left\lfloor n/5 \right\rfloor + \left\lfloor n/5^2 \right\rfloor + \left\lfloor n/5^3 \right\rfloor + \ldots + \left\lfloor n/5^k \right\rfloor such that 5^k \le n

Here is some explanation. The term \left\lfloor n/5^i \right\rfloor finds the number of integers between 1 and n that 5^i divides. For example for n = 27, \left\lfloor 27/5 \right\rfloor = 5, that is there are 5 integers divisible by 5 within the range 1 to 27, in other words there is 5 integers which has the factor 5 once, which are 5, 10, 15, 20, and 25. Also \left\lfloor 27/5^2 \right\rfloor = 1 , that is, there are 1 integer divisible by 25 within the range 1 to 27, or in other words there is one integer which has the factor 5 twice. The total number of occurrence of the factor 5 is calculated by computing the above formula, which divides and adds the number of times a power of factor 5 occurs in factorial of n. Therefore there are a total of 5 + 1 = 6 number of times the factor 5 occurs in the entire series of 1 to 27. Therefore there are 6 trailing zeros in 27! and 27! = 10888869450418352160768000000 which has 6 trailing zeros.

The implementation is pretty straight forward.

Sourcecode

#include <stdio.h>

/* long int n : the input factorial integer
 * long int i : holds value 5^k , the divisor of `n' to
 *              find the number of times the factor 5 occurs
 *              in the factorial of `n'
 * long int c : number of times the 5 occurs as a factor in the
 *              factorial of `n'
 * long int t : the number of times the factor 5^i occurs in the `n!'
 */
int
main (void)
{
  long int n, i = 5, c = 0, t;

  printf ("\nEnter n: ");
  scanf ("%ld", &n);
  do
    {
      t = n / i; /* computes floor (n/i)  where i=5^k */
      c += t;    /* update the number of occurrence of factor 5 */
      i *= 5;    /* update `i' to be the next power of 5 */
    }
  while (t != 0);

  printf ("Number of trailing zeros in %ld! : %ld\n", n, c);

  return 0;
}

Output

Some sample outputs are given below.


run 1
  Enter n: 3
  Number of trailing zeros in 3! : 0

run 2
  Enter n: 6
  Number of trailing zeros in 6! : 1

run 3
  Enter n: 15
  Number of trailing zeros in 15! : 3

run 5
  Enter n: 60
  Number of trailing zeros in 60! : 14

run 6
  Enter n: 100
  Number of trailing zeros in 100! : 24

run 7
  Enter n: 1000
  Number of trailing zeros in 1000! : 249

run 8
  Enter n: 5000
  Number of trailing zeros in 5000! : 1249

run 9
  Enter n: 10000
  Number of trailing zeros in 10000! : 2499

run 10
  Enter n: 12345678
  Number of trailing zeros in 12345678! : 3086416

Links and References

2 thoughts on “Number of trailing zeros in factorial of an integer

    1. Great site. Once you know the algorithm you can implement it in any language. For example here are some quick bash implementations.

      #!/bin/bash
      
      num=$1
      i=5
      t=1
      while [ $t -ne 0 ]
       do
         t=$((num/i))
         count=$((count+t))
         i=$((i*5))
      done
      
      echo "Trailing zeros of $num ! = $count"
      

      Or we can use the factor command to count the number of 5 in each of the integer. Although this process is extremely inefficient as it will compute the factor of each integer from 1 to n, but still it works.

      #!/bin/bash
      
      num=$1
      count=0
      
      for ((i=1; i<=num; i++))
        do
          this_count=$(factor $i | cut -d':' -f 2 | tr ' ' '\n' | grep -c "\<5\>")
          count=$((count + this_count))
          this_count=0
      done
      
      echo "$count"
      

      Thanks for visiting.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s