In the input section, it says There is a single positive integer T on the first line of input (equal to about 100000). It stands for the number of numbers to follow. Then there are T lines, each containing exactly one positive integer number N, 1 <= N <= 1000000000.
How can I get this without the use of a large array?
we never need to store these inputs in array , just run a loop for a test cases, take input in normal variable and give a output then go for next test case do the same process or i will advice you once to check the code of others of any different question.
Then I suggest you find the implicit mathematical law of the problem. The problem is to find the number of zeros at the end of the factorial of n. You are very smart. You know how many factors are 5 in the number of 1-n, so the answer is very obvious.
Instead of counting one by one, consider the whole.
For example if n is 54, then no. of 5’s in [1,54] are {5,10,15,20,25,30,35,40, 45,50} i.e.10, 54/5, but 50 and 25 itself has 2 5’s, so there are total 12 5’s, which is 10 + 2 i.e. 54/10 + (54/10)/10.
For eg: how many 2’s are in 8!? numbers having 2 are {2,4,6,8} but 4 and 6 have 2 2’s so ans is 6 i.e. 8/2 + (8/2)/2…
This is general way by which you can find multiples of x in range[a,b]. So you can apply it here.
Ans will be b/x + b/x*x…upto b!=0 and minus one which are in before a using same thing.
I did this problem in spoj and took couple of hours getting this
#include <stdio.h>
int F(int);
int Z(int);
int main()
{ int N,fact,ans;
printf(“enter the N”);
scanf("%d",&N);
fact=F(N);
ans=Z(fact);
printf("%d",ans);
return 0;
}
int F(int x)
{
if(x==0||x==1)
return 1;
else
return x*F(x-1);
}
int Z(int x)
{int rem,count=0;
while(x!=0)
{rem=x%10;
x=x/10;
if(rem!=0)
break;
count++;
}
return count;
}
Why it is wrong even it is working