I am complete newbie on this website. I tried to solve some problems on practice section (easy ones). I pick up an easy problem I write it in VC++, I compile it and test it my computer but when i try to submit code it says wrong answer. So can you please tell me what’s wrong with my code…
Firstly, compiling your code locally on VC++, can produce undesired results, like weird Runtime errors and some other things that are only compiler dependent which can be very annoying…
Secondly, on Codechef, in order to get AC for a problem, you need to strictly respect the I/O format. On this case, you are not printing a new line after your answers… To fix that, you can simply do:
cout<<count_2<<endl;
And lastly, but the most important thing… Codechef is an algorithms website, which means that above working code you must have a correct and working algorithm…
I saw your submissions which you have made for this problem .
You are not getting WA for any CodeChef technicality reason . You are getting WA because your algorithm is wrong .
Both the functions factor_5 and factor_2 are logically wrong .
The number of times the factorial of a number is divisible by a prime p is given by ,
floor(n/p) + floor( n/p^2) + floor(n/p^3) …
I uses the point that 0 at the end of factorial will only appear if their will be multiply of 2 and 5 or their multipliers. if their are 5 , 2 and 4 , 5 the there will be 4 zeros…
Can you please help me to figure out my logical error… I will be thankful to you.
here is full code i have written…
# include
#include
using namespace std;
int factor_2(unsigned int);
int factor_5(unsigned int);
int main()
{
unsigned int a[6];
for(int i=0;i<6;i++)
cin>>a[i];
for(int i=0;i<6;i++)
{
int count_2 = factor_2(a[i]);
int count_5 = factor_5(a[i]);
if(count_2<count_5)
cout<<count_2;
else
cout<<count_5;
}
return 0;
}
int factor_2(unsigned int a)
{
int count = 0;
unsigned int i;
for(unsigned int j=1;j<=a;j++)
{
i=j;
while(i%2==0)
{
count++;
i=i/2;
}
}
return count;
}
int factor_5 (unsigned int a)
{
int count = 0;
unsigned int i;
for(unsigned int j=1;j<=a;j++)
{
i=j;
while(i%5==0)
{
count++;
i=i/5;
}
}
return count;
}
Suppose the number is 132 .
floor(132/5) = 26 . This accounts for occurrence of one 5 in 5 , 10 , 15 … 130.
floor(132/25) = 5 . This accounts for an extra 5 in 25 , 50 , 75 , 100 , 125 .
floor(132/125) = 1 . This accounts for still extra 5 in 125 .
Summing 26 + 5 + 1 = 32 gives the number of times 5 is a factor of 132 factorial . The number of times 2 is a factor of given number N will always be greater than or equal to number of times 5 is a factor N . Hence you can completely do away with the function factor_2 .
The function factor_5(int n ) should look like ;
factor(int n) {
int pow = 5;
int ans = 0;
while(pow<n) {
ans += n/pow ;
pow *= 5;
}
return ans ;
}
There is no need for two loops in factor_5 .
you also need to take care of range of numbers . So in java i use long which is 64 bit integer . You should use 64 bit numbers to avoid going out of range error .