ZEROES-EDITORIAL

PROBLEM LINK

Practice http://www.codechef.com/INLO2015/problems/ZEROES

Contest http://www.codechef.com/INLO2015

Editorialist: Ravit Singh Malik http://www.codechef.com/users/ravit007

DIFFICULTY:

easy

PREREQUISITES:

Maths

PROBLEM

You are required to find the number of trailing zeroes of F(n) = 1^12^23^3*…*N^N,

QUICK EXPLANATION

suppose uou have to find the number of zeroes in a product. 24*32*23*19=( 2^3*3^1)*2^5*23*19 as you can notice, this product will have no zeroes because it has no 5 in it.

however, if you have expression like: 81523172522
it is equal to 2^3
3^15^123175^22^111^1

Zeroes are formed by the cobination of 2*5. Hence,the number of zeroes will depend on number of pairs
of 2’s and 5’s that can be formed.
In the above product, there are four twos and three fives.Hence, ther will be 3 Zeroes in the product.

EXPLANATION:

In the given problem You are required to find the number of trailing zeroes of F(n) = 1^12^23^3*…*N^N,
so, if n=32

F(n) = 1^12^23^3*…32^32,
so,the fives will be less than twos. Hence, we need to count only the fives.
Thus: 5^5
10^1015^1520^2025^2530^30
give us: 5+10+15+20+25+25+30
we take 25 two times because it have two fives each.
thus the f(n) has 130 trailing zeroes.

Pseudocode:

Start

input test cases t

while(t–)

input n

begin of loop

for(a=5,b=0;a<=n;a+=5)

l=1;

k=a/5;

while(k%5==0)

{

k=k/5;

l++;

}

b=b+a*l;

end of loop

print b

end

end

//