Need help in question SINS

help
, ,
1

I’ve got a problem . it’s called deadly sins, here’s the link: https://www.codechef.com/problems/SINS/
Here’s the right code :

#include<stdio.h>
 
int GCD(int x, int y){
 if(y==0)
 return x;
 else
 return (GCD(y,x%y));
}
int main() {
  int X,Y,T,result,gcd;
  scanf("%d",&T);
  for(;T>0;T--){
  scanf("%d %d",&X,&Y);
  if(X>Y){
    gcd = GCD(X,Y);
    }
    else{
      gcd = GCD(Y,X);
    }
    printf("%d\n",2*gcd );
   }
 
  return 0;
}

I don’t understand the logic of this code (the gcd() and printf) someone please explain this to me.
And here’s my code:

  #include <stdio.h>
     //Compiler version gcc 6.3.0
     
     int main(void)
     {
     	int m, b, t, x, y, z;
     	scanf ("%d",&t);
     	z=t;
     	scanf ("%d%d",&m, &b);
     next :	while(m!=b)
     	{
     	if(m>b)
     	m=m-b;
     	if(m<b)
     	b=b-m;
     	t--;
     	if(m==b)
     	{x=m;
     	y=b;
     		printf("%d\n",x+y);
     		if (z>1)
     	{
     	scanf("%d%d",&m, &b);
     	goto next;
     	} 
     	} 
     	}
     	
     	
     	return 0;
     }

I know it’s wrong but can somebody help me fix this code without changing the logic.

1 Like
2

In the correct code gcd() is a function which computes the greatest common divisor of two numbers( refer https://www.geeksforgeeks.org/c-program-find-gcd-hcf-two-numbers/ )
The problem statement says that we have to make X and Y equal. Your solution gets a TLE verdict because X and Y are as large as 10^9 so repeated subtraction operations will consume a lot of time. That’s why you need to make a small observation. At the end both will be left with same chocolates which is the GCD of X,Y. You can take a look at given examples and verify it.
As both are left with gcd total candies left are gcd+gcd i.e. 2gcd. printf statement at the end outputs the final answer( 2gcd).