# Factorial- FCTL. my code gives TLE. bt it runs fine on ideone for the given sample input. Can anyone help me in optimising the code.

I checked the code in my computer also for different inputs.

`````` enter code here
#include<stdio.h>
#include<iostream>
#include<math.h>
#include<map>

using namespace std;
int main()
{
unsigned long test;
scanf("%lu",&test);
unsigned long clll[test];
unsigned long check;
map<int,long> m;
for(unsigned long i=0;i<test;i++)
{
unsigned long Num;
scanf("%lu",&Num);
m[2]=0;
m[5]=0;
for(unsigned long j=1;j<=Num;j++)
{
check=j;
while((check%2==0)&&(check>0))
{
m[2]++;
check/=2;
}
while((check%5==0)&&(check>0))
{
m[5]++;
check/=5;
}
}
clll[i]=m[2]>m[5]?m[5]:m[2];
}
for(int ni=0;ni<test;ni++)
printf("%lu\n",clll[ni]);
return 0;
}``````

if you look at the factorials carefully:

``````1-1
2-2
3-6
4-24
5-120
6-720
.
.
9-362880
10-3628800
``````

The trailing zeros increase for the multiples of 5. another thing to be noted is that the value increases by 2 for every 5 turns,(25,50,75…)

working solution: http://www.codechef.com/viewsolution/3250906

1 Like

Hi,

As pointed out by @squal “the number of zeroes increase by 2 for every 5 turns”,Solving this problem may come in handy if we follow very interesting property of a prime number and factorials.

Since N! = 1X2X3X…X(n-1)X(n)

so the zeroes come at the end when we encounter pair of 2 and 5.Let us say there are T number of twos in factorising N! and F number of fives. ans we can be pretty sure that T>F as there will obviously be greater number of twos. Hence we need to fing the Power of 5 we get in factorising N!.

As I mentioned earlier there is a very interesting property that for any N! the highest power of a prime number ‘p’ that divides N! can be given by

``````HIGHEST POWER= N/p + N/(p^2) + N/(p^3).....+N/(p^k)
for k such that p^(k+1)>N
``````

so here we need to find the highest power of 5 that divide the given factorial. for instance 100 and here k=2 as 5^(2+1)=125>100

so Highest power=100/5+100/25 = 20 + 4 =24

since the highest power is number of zeroes so 24 is number of trailing zeroes in 100!.

Hope you understood.

Happy coding

1 Like

Thanx for ur help.