The problem here is divide all numbers by some constant so that the divisions have no remainder. We produce the smallest result by dividing by a number that is as large as possible, that is the greatest common divisor. The greatest common divisor can be computed efficiently by Euclid’s algorithm, but in this case it was fast enough to simply check all numbers from 1 to 1000 for divisibility.
note on my code: the gcd block is taken from wiki url i have shown above. and main block is my c++ code. i initialised arr of 50 ingredients and saved ingredients in it. and then i have taken cmmn - the greatest common divisor for ingredients in the array. if cmmn==1 then the array has no gcd, so i just printed out the arr itself. if cmmn is equal to ingredients of arr then yes==1, which means that all ingredients in the arr are same numbers, for ex 4 as given in the codechef sample output, if so i printed out 1 for every ingredient of arr. and if there exist gcd(here cmmn) other than 1 and ingredints itself, then print out arr[i]/cmmn. that is it.
NOTE: i still have difficulty in understanding the binary gcd algo. can anyone pls post the easier way to learn binary gcd algo. tnx
Can anyone please tell me :-
I have run my code several times in my laptop with several cases and does not encountered any problem.But after submitting it I got wrong answer… Please Check my code and please inform me about my mistake and the particular case … Waiting for your reply… CodeChef: Practical coding for everyone
my code is giving correct answers but in uploadinong your compiler is saying wrong plasee check it or tell me the example which is giving wrong answer #include <stdio.h> #include <stdlib.h>
void input(void);
int main()
{
int n,i;
printf(“enter the number the test case\n”);
scanf("%d",&n);
for (i=0;i<n;i++)
{
input();
}
return 0;
}
void input(void)
{
int i,n,b,a[50];
int j=0,count=0 ;
printf(“enter the number of items between 2 to 50 :”);
scanf("%d",&n);
printf(“enter the numbers “);
for(i=0;i<n;i++)
{
scanf(”%d”,&a[i]);
if(i==0)
{
b=a[0];
}
if(i>0)
{
if(b>a[i])
b=a[i];
}
}
for(i=0;i<n;i++)
{
while(1)
{
j++;
if(bj<=a[i])
{
if(bj==a[i])
break;
}
if(b*j>a[i])
{
for(i=0;i<n;i++)
printf("%d ",a[i]);
count ++;
break;
}
}
if (count==1)
break;
my code is giving correct answers but when i am uploading in your compiler its saying wrong answer please check it or tell me the example which is giving wrong answer
Add a check that if minimum element isn’t gcd, check if any factor of it is GCD of all. (Eg, here 15 isn’t GCD, but its factor 5 is GCD of all elements).