FCTRL - Editorial

Could someone please tell me what is wrong with this code.
Basic idea behind my logic is i calculate the factorial by multiplying all numbers from 1 to N(N being the number itself) and at each juncture i check the condition whether the factorial at that particular instant is divisible by 10 leaving a remainder of 0 and if it is i am calculalating the sum at the end.
here goes the code.

#include

using namespace std;

int main()
{
int a,b,c,fact=1,sum=0,e=0;
cin>>a;//for taking in the total number of input
int f=0;
for(b=0;b<a;b++)
{
cin>>c;//selecting each input value

for(int d=1;d<=c;d++)
{f=0;
    fact=fact*d;
    e=fact;
    while(f==0)
    {
    if(fact%10==0)
    {
        sum++;
        fact=fact/10;
        f=0;
    }
    else{f=1;}}
    fact=e;
}
cout<<sum<<endl;
sum=0;
fact=1;}}

@dark_pharoah Your logic is correct but it takes more time, quite cumbersome and is prone to mistakes. The logic is 0’s are formed by combination of 5’s and 2’s(since 5x2=10) Agree? For example 30=2x3x5(0 is formed by 5 and 2). So, we have to find min(number of 2’s,number of 5’s) in n! so that they can combine to form 0’s. That can be found by:-

number of 2’s->[n/2]+[n/2^2]+… until it is 0

number of 5’s->[n/5]+[n/5^2]+… until it is 0, Here [] is floor

The reason for this is explained clearly in the above editorial. Have a look at it.

We can observe that number of 5’s will be less as it’s a big number(so just calculate number of 5’s)

So, the code goes as follows:- Click Here

1 Like

#include
using namespace std;

int mmofive( long int t)
{ int n=0, pof=5;
while ( t/pof>0)
{pof*=5; n++;}
return n-1;
}//max divisible multiple of 5 (power)

int main()
{
long int n,t; int i,j;
int trailingzero=0;
cin>>n;

const long int f=n;
int A[f];
for ( i=0; i<n; i++)
{cin>>t;
for(j=5;j<=5^mmofive(t);j*=5)
{trailingzero+=t/j;}
A[i]=trailingzero;
trialingzero=0;
}

for (long int i=0; i<n; i++)
{cout<<A[i]<<endl;}

return 0;
}

WHY NOT WORKING? :((
i devised the same logic as expected.
but it says it exceeds time limit.
i believe, even if the number is as large as 100000000 , on dividing by 5 continuously, the final output should take quite less time.

#include <stdio.h>

int main()
{
int n = 4617, troll = 0, i=1, num = 5,quotient;

while(quotient > 1)
{
    i = num * i;
    //printf("%d",i);
    quotient = n/i;
    troll = troll + quotient;
}
printf("%d\n",troll);

return 0;

}

Help in C#!!
My Code is Running successfully, giving desires o/p
But on submit getting error as Wrong Answer.

using System;
public class Test
{
public static void Main()
{// your code goes here
int n = Convert.ToInt32(Console.ReadLine());
int[] N = new int[n];
for(int i=0;i<N.Length;i++)
{
N[i] = Convert.ToInt32(Console.ReadLine());
}
for(int i=0;i<N.Length;i++)
{
int fact = 5;
int trailingzeros = 0;
while(N[i]>fact)
{
trailingzeros = trailingzeros + (N[i]/fact);
fact = fact*5;
}
Console.WriteLine(trailingzeros);
}
}
}

Why doesn’t this work?

#include <iostream>
using namespace std;
int main()
{
	// your code goes here
int f=9;
	do
    {
	    int n;
	    cin>>n;
	    int fac=1;
	    for(int i=1; i<=n; i++)
	    {
	        fac= fac*i;
	    }
	        int cont=0;
            while(fac%10==0)
            {
                cont++;
                fac= fac/10;
            }
	        cout<<cont<<endl;

	} while(f==9);
	return 0;
}

Why can’t I simply find the answer by cout<<(input/5)+(input/25); please explain it to me somebody? Why do I need to divide it if I can find the answer by doing the above method. But if I am trying to do (input/5)+(input/25) I am getting WA. Please help!

think about it when n is 125

1 Like

Very nicely explained

#include <stdio.h>

int main(void) {
long long int n;
int k;

scanf("%d", &k);
while(k--)
{
    long long int count=0;
    long long int temp=5;
    scanf("%lld",&n);
    while(n/temp!=0)
    {
        count = count+ (n/temp);
        temp*=5;
    }
    printf("%lld\n",count);
}
return 0;

}

Can anyone tell me why i an getting a WA on this?

#include<bits/stdc++.h>
using namespace std;

long long int answer(long long int num)
{
    long long int track_end=5,ans=0;
    for (long long int i = 0; track_end <num; ++i)
    {
        ans=ans+(num/track_end);

        track_end=track_end*5;
    }

    return ans;
}






int main()
{
    long long int n; cin>>n;

    while(n--)
    {
        long long int number; cin>>number;
       cout<<answer(number)<<endl;
        
    }    


    return 0;
}

Change it to track_end<=num. I think that will help.

1 Like

Thanks bro

This a really simple solution to it in Java

  public static void main (String[]args) throws java.lang.Exception
  {
    // your code goes here
    Scanner in = new Scanner (System.in);
    int t = in.nextInt ();
    for (int i = 0; i < t; i++)
      {
          int n=in.nextInt();
          int sum=0;
        while (n/5>0)
        {
         sum+=n/5;
         n/=5;
        }
        System.out.println(sum);
      }
  }

it should be (input/5)+(input/25)+(input/125)+(input/625)+(input/3125)...

Create a while loop like this:

   int n=in.nextInt();
          int sum=0;
        while (n/5>0)
        {
         sum+=n/5;
         n/=5;
        }
        System.out.println(sum);

l=[]
n=int(input())
for i in range(n):
l.append(int(input()))
for i in l:
k=5
r=0
while(k<i):
r+=i//k
k*=5
print( r )

//this code works fine in other editor but gives error in codechef why??
///sorry for indentation in comments

1 Like

the actual formula is n/5 + n/5^2 + n/5^3+… up until n becomes 0.So you need to cut off that j loop and start calculation with N
you can check my code here : CodeChef: Practical coding for everyone

1 Like

I am using this code for the problem.

# cook your dish here

for _ in range(int(input())):
    num = int(input())
    zeroes = 0
    power_div = 5
    while num / power_div > 1:
        zeroes += int((num / power_div))
        power_div *= 5
    print(zeroes)

I tested in my machine for the numbers in the editorial, it is working fine for those inputs

I get

4
24
249
1151

for the inputs

23
101
1000
4617

But the submission is returning Wrong answer. Can someone point out the error? Thanks in advance :pray:

just change
while num / power_div > 1:
to
while num // power_div > 0:

It worked but I do not understand why