Calculate number of trailing zeros in n!

Q.There is a single positive integer T on the first line of input. It stands for the number of numbers to follow. Then there are T lines, each containing exactly one positive integer number N, 1 <= N <= 1000000000. For every number N, output a single line containing the single non-negative integer corresponding to number of zeros in N! .

Sample Input:

6

3

60

100

1024

23456

8735373

Sample Output:

0

14

24

253

5861

2183837

Solution:

A trailing zero is always produced by prime factors 2 and 5. If we can count the number of 5s and 2s, our task is done. Consider the following examples.

n = 5: There is one 5 and 3 2s in prime factors of 5! (2 * 2 * 2 * 3 * 5). So count of trailing 0s is 1.

n = 11: There are two 5s and three 2s in prime factors of 11! (2 ^8 * 3^4 * 5^2 * 7). So count of trailing 0s is 2.

We can easily observe that the number of 2s in prime factors is always more than or equal to the number of 5s. So if we count 5s in prime factors, we are done. How to count total number of 5s in prime factors of n!? A simple way is to calculate floor(n/5) /*floor means greatest integer function*/. For example, 7! has one 5, 10! has two 5s. It is done yet, there is one more thing to consider. Numbers like 25, 125, etc have more than one 5. For example if we consider 28!, we get one extra 5 and number of 0s become 6. Handling this is simple, first divide n by 5 and remove all single 5s, then divide by 25 to remove extra 5s and so on. Following is the summarized formula for counting trailing 0s.

Trailing 0s in n! = Count of 5s in prime factors of n! = floor(n/5) + floor(n/25) + floor(n/125) + ....

code:

#include <iostream>

using namespace std;

int factorialzero(int);

int main()

{

int t;

cin >> t;

int a[t];

for(int i=0;i<t;i++)

cin>>a[i];

for(int i=0;i<t;i++)

{

cout << factorialzero(a[i]) << endl;

}

return 0;

}

int factorialzero(int n)

{

int flag=0;

for(int i=5;n/i>=1;i=i*5)

{

flag += n/i; //equivalent to flag = flag + n/i;

}

return flag;

}

#factorial #loop #function #algorithms