Time limit getting exceeded and also the program not seeming to work for N>=60 in FCTRL question in easy practice problems section. What is wrong with my code?
I ran it on gdb and found that as your N goes above 60 then t and p become very large and reach the max value they can hold and hence program isn’t working for N>60. I saw the solution in the submissions column of the problem but i am not able to comprehend it. Pls explain what the mistake is in my program and what is the best way to implement it . thanks …
#include<stdio.h>
int z(unsigned long);
int main(void)
{
unsigned long t=0,i;
scanf("%lu",&t);
for(i=0;i<t;i++)
{
unsigned long n;
scanf("%lu",&n);
if(n>=1&&n<=1000000000)
{
int ctr=z(n);
printf("%d\n",ctr);
}
else
return 0;
}
return 0;
}
int z(unsigned long n)
{
int tz=0;
unsigned long long t,p=1;
t=n;
while(1)
{
printf("n=%lu t=%llu tz=%d p=%llu\n ",n,t,tz,p);
n--;
p=t*n;
while(p%10==0)
{
p/=10;
tz++;
}
t=p;
if(n<=1)
break;
}
return tz;
}
You cannot manually expect to find factorial and print the answer.To find the no.of times a number occurs in n! we have a function f(n,x) which is the no of occurrences of x in n!.
For example if f(10,2) is 8 then it means that 10! is divisible by 2^8 ,2^7 but not by 2^9.
Now f(n,x)=floor(n/x^1)+floor(n/x^2)+floor(n/x^3)… …(this is a formula)
Since u have to find the no of zeroes in factorial the answer will be min(f(n,2),f(n,5)).
But obviously f(n,5) will be smaller than f(n,2). Thus the answer is f(n,5) .
But the formula is infinite .But note that once power of 5 exceeds n u do not have to calculate further.
1 Like
Factorial is a very fast growing function.
eg 100!=93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000.
Therefore, you cannot solve this problem by just calculating factorials.
Note, a zeroes at the end means that the number is divisible by some powers of 10.
And every 10 is formed by a combination of 2 and 5.Therefore,if we can find the number of times, 5 have been multiplied with 2 in the factorial.It is the required answer.
1 Like