Number of trailing zeros in factorial of an integer


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

About these ads

About phoxis

Homo-sapiens
This entry was posted in Coding Discussions, Computer Science, Others and tagged , , , , . Bookmark the permalink.

2 Responses to Number of trailing zeros in factorial of an integer

  1. Cassie says:

    Fantastic post! This site also gives a good explanation of how to come up with the algorithm, and also an implementation in Java:

    http://www.programmerinterview.com/index.php/java-questions/find-trailing-zeros-in-factorial/

    • phoxis says:

      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