Error in calculating GCD and LCM

general
, , ,
1

I have written the below code to calculate the GCD and LCM.

It works fine for the given set of inputs in the question as well as for some other inputs which i tried.

If when running on codechef it says Wrong Answer.

Not sure what is causing this error.

Any suggestion would be helpful.

import java.io.BufferedReader;

import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;

public class GCDandLCM
{

public static void main(String[] args) throws Exception 
{
	InputStreamReader isr = new InputStreamReader(System.in);
	BufferedReader br = new BufferedReader(isr);
	
	PrintWriter pw = new PrintWriter(System.out);
	
	int testcases = Integer.parseInt(br.readLine());
	int gcd = 0;
	
	while(testcases-- > 0)
	{
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int a = Integer.parseInt(st.nextToken());
		int b = Integer.parseInt(st.nextToken());
		
		for (int i = 1; i <= a; i++)
		{
			if(a % i == 0 && b % i == 0)
				gcd = i;	
		}
		
		pw.println(gcd + " " + a * b / gcd);
	}
	
	pw.flush();

}

}

2

Dont print superfluous print statements like “Gcd=”+gcd etc. It causes WA. Print EXACTLY whats asked in the output section.

3

Your algorithm looks correct. Since you have not given the link of the problem you are referring to, I would suggest that you should check the constraints given in the problem statement. Since you have used int, it can store values up to approximately 10^9.

Also, your algorithm is inefficient as it checks the divisibility for every number. You can use Euclid’s algorithm to make it run faster.

A recursive implementation is as follows :

int gcd(int a , int b)
{
    if(a % b == 0)
        return b;
    return gcd(b , a % b);
}
1 Like
4

pw.println(gcd + " " + a * b / gcd);

The above statement is only printing GCD and LCM with a " " between them as asked in the question.

please correct if it is wrong interpretation of the output

1 Like
5

Please post the question link. You got back after too long time- I lost track of the question.

6

Please find the link below.

https://www.codechef.com/viewsolution/17080876