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.

general
, , ,
1

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;
}
2

@azimuthal:

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
3

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

Hope you understood.

Happy coding :slight_smile:

1 Like
4

Thanx for ur help.

5

your welcome :slight_smile: