You are not logged in. Please login at www.codechef.com to post your questions!

×

[closed] 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;
}

asked 13 Jan '14, 14:15

azimuthal's gravatar image

2★azimuthal
714615
accept rate: 0%

closed 24 Jan '14, 23:15

The question has been closed for the following reason "The question is answered, right answer was accepted" by azimuthal 24 Jan '14, 23:15


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

link

answered 13 Jan '14, 17:35

c0d3_k1ra's gravatar image

2★c0d3_k1ra
175118
accept rate: 11%

Thanx for ur help.

(13 Jan '14, 22:14) azimuthal2★

your welcome :)

(14 Jan '14, 12:51) c0d3_k1ra2★

@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

link

answered 13 Jan '14, 15:05

squal's gravatar image

4★squal
1.2k41533
accept rate: 14%

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×1,918
×235
×46
×1

question asked: 13 Jan '14, 14:15

question was seen: 1,331 times

last updated: 24 Jan '14, 23:15