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

CodeChef Problem Statement http://www.codechef.com/problems/FCTRL
Dr. Math Forums http://mathforum.org/library/drmath/view/66749.html
Wikipedia Link: http://en.wikipedia.org/wiki/Trailing_zero

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

Cassie says:

November 28, 2012 at 2:11 pm

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/

Reply
1. phoxis says:
  
  November 28, 2012 at 2:44 pm
  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.
  Reply

Number of trailing zeros in factorial of an integer

Solution

Sourcecode

Output

Links and References

Share this:

Like this:

Related

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

Leave a Reply Cancel reply