7 replies to this topic

[Hacker4life]

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.

[chili5]

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

[Hacker4life]

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

[chili5]

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

[Hacker4life]

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

[WingedPanther73]

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.

[Hacker4life]

too slow

[chili5]

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