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: . 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 . 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:

such that

Here is some explanation. The term finds the number of integers between 1 and `n` that divides. For example for `n = 27`, , 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 , 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

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/

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

Or we can use the

factorcommand 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.Thanks for visiting.