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.

 0 I checked the code in my computer also for different inputs.  enter code here #include #include #include #include using namespace std; int main() { unsigned long test; scanf("%lu",&test); unsigned long clll[test]; unsigned long check; map m; for(unsigned long i=0;i0)) { m++; check/=2; } while((check%5==0)&&(check>0)) { m++; check/=5; } } clll[i]=m>m?m:m; } for(int ni=0;ni

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

 1 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 :) answered 13 Jan '14, 17:35 175●1●1●8 accept rate: 11% Thanx for ur help. (13 Jan '14, 22:14) your welcome :) (14 Jan '14, 12:51)
 1 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 answered 13 Jan '14, 15:05 4★squal 1.2k●4●15●33 accept rate: 14%

### Follow this question

By Email:

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

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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