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


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.