FCTRL - TLE

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

thanks for the answer