Jump to content


Check out our Community Blogs

Register and join over 40,000 other developers!


Recent Status Updates

View All Updates

Photo
- - - - -

Factorial Task


  • Please log in to reply
7 replies to this topic

#1 Hacker4life

Hacker4life

    CC Resident

  • Advanced Member
  • PipPipPipPip
  • 77 posts
  • Location:Serbia
  • Programming Language:C, C++, Delphi/Object Pascal, Pascal, Others
  • Learning:C, Java, C++, (Visual) Basic, Python, Delphi/Object Pascal, Pascal, Assembly, Others

Posted 14 August 2012 - 06:08 AM

n! = n*(n-1)*(n-2)....*1

write a program which tells how many ending zero in n!


INPUT:
A single line contains a number N (1<=N<=2000000000)



OUTPUT:
A single line contains a number of ending zero in N!




Input:

18
Output:

3

program zad;
var n,i,s:longint;
k:integer;
begin
read(n);
k:=0;
for i:=2 to n do begin
						 if i mod 5=0 then begin
											 s:=i;
												 repeat
													 k:=k+1;
																 s:=s div 5;
												 until
												 s div 5=0;
														 end;
					 end;
write(k);
end.
My code does not work. Do you have a faster solution ?
It has TLE- time limit exceeded.
  • 0

#2 chili5

chili5

    CC Mentor

  • Expert Member
  • PipPipPipPipPipPipPipPip
  • 3038 posts
  • Programming Language:Java, C#, PHP, JavaScript, Ruby, Transact-SQL
  • Learning:C, Java, C++, C#, PHP, JavaScript, Ruby, Transact-SQL, Assembly, Scheme, Haskell, Others

Posted 14 August 2012 - 08:23 AM

I remember this problem - the recursive solution will also timeout.

int fact(int n) {
		 assert(n >= 0);
		 if (n<=1) return 1;
		 return n * fact(n-1);
}

Try that out and watch it timeout. What you need to do is write an iterative solution like this:

int fact2(int n) {
	    assert(n>=0);
	    int fact = 1;

	    while(n>= 2){
			  fact = fact * n;
			  n--;
	    }
	    return fact;
}

  • 0

#3 Hacker4life

Hacker4life

    CC Resident

  • Advanced Member
  • PipPipPipPip
  • 77 posts
  • Location:Serbia
  • Programming Language:C, C++, Delphi/Object Pascal, Pascal, Others
  • Learning:C, Java, C++, (Visual) Basic, Python, Delphi/Object Pascal, Pascal, Assembly, Others

Posted 14 August 2012 - 12:24 PM

nope, input is a long number so you cant do that. I think there is a formula or something
  • 0

#4 chili5

chili5

    CC Mentor

  • Expert Member
  • PipPipPipPipPipPipPipPip
  • 3038 posts
  • Programming Language:Java, C#, PHP, JavaScript, Ruby, Transact-SQL
  • Learning:C, Java, C++, C#, PHP, JavaScript, Ruby, Transact-SQL, Assembly, Scheme, Haskell, Others

Posted 14 August 2012 - 12:43 PM

There is this: http://en.wikipedia....ues_of_argument

Another thing you can do is approximate n! with stirling's formula

n! ~= sqrt(2*Pi*n)*(n/e)^n
  • 0

#5 Hacker4life

Hacker4life

    CC Resident

  • Advanced Member
  • PipPipPipPip
  • 77 posts
  • Location:Serbia
  • Programming Language:C, C++, Delphi/Object Pascal, Pascal, Others
  • Learning:C, Java, C++, (Visual) Basic, Python, Delphi/Object Pascal, Pascal, Assembly, Others

Posted 14 August 2012 - 01:11 PM

Can u give me more details, i havent finished school yet so idk what most of those things are in wikipedia formulas
  • 0

#6 WingedPanther73

WingedPanther73

    A spammer's worst nightmare

  • Moderator
  • 17757 posts
  • Location:Upstate, South Carolina
  • Programming Language:C, C++, PL/SQL, Delphi/Object Pascal, Pascal, Transact-SQL, Others
  • Learning:Java, C#, PHP, JavaScript, Lisp, Fortran, Haskell, Others

Posted 15 August 2012 - 03:44 PM

Loop through the numbers from 1 to n. For each one, find the number of 5's in its factorization, and add 1 to the zero count for each.
  • 0

Programming is a branch of mathematics.
My CodeCall Blog | My Personal Blog

My MineCraft server site: http://banishedwings.enjin.com/


#7 Hacker4life

Hacker4life

    CC Resident

  • Advanced Member
  • PipPipPipPip
  • 77 posts
  • Location:Serbia
  • Programming Language:C, C++, Delphi/Object Pascal, Pascal, Others
  • Learning:C, Java, C++, (Visual) Basic, Python, Delphi/Object Pascal, Pascal, Assembly, Others

Posted 16 August 2012 - 01:57 AM

too slow
  • 0

#8 chili5

chili5

    CC Mentor

  • Expert Member
  • PipPipPipPipPipPipPipPip
  • 3038 posts
  • Programming Language:Java, C#, PHP, JavaScript, Ruby, Transact-SQL
  • Learning:C, Java, C++, C#, PHP, JavaScript, Ruby, Transact-SQL, Assembly, Scheme, Haskell, Others

Posted 16 August 2012 - 02:41 PM

Try playing around with Stirling's approximation. It won't give you an exact answer but you might be able to get the right answer by rounding up to the nearest 10th (depends how much precision you keep).

Maybe try a dynamic programming approach? What is the bounds given on n? [1, 100]? This might (probably) will use too much memory though. Make an array of size 100 and store the factorials computed.

Say you have this array (of size 5)
[1,1,0,0,0,0]

0! = 1
1! = 1

Are the computed base cases. Also keep the index of the last factorial that has been calculated. When the test script asks for fact(5) you already have fact(0), fact(1) then you can compute fact(2), fact(3), fact(4) and fact(5) with just 4 multiplications instead of 5 for fact(5). Then say it asks for fact(7) you only have to do two multiplications instead of 7. Might work.

Say you have these numbers to find the factorials of:
5 (3 multiplications needed)
7 (2 multiplications needed)
9 (2 multiplications needed)
3 (0 multiplications needed - just return the answer)
81 (71 multiplications needed)
76 (0 multiplications needed - would have been precomputed with fact(81))
30 (0 multiplications needed - would have been precomputed with fact(81))
85 (4 multiplications needed)

Memory space might be an issue though.

Might be even faster is to assume the worstcase - precompute and store fact(100) and all the lower answers will be computed and if asked for just have to return them. No calculations necesary.

I coded this on my computer and was able to compute fact(100) in 00:00:00.020. Then it only took 00:00:00.003 to calculate factorial(99).
  • 0




Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download