🔗 Greatest Common Divisor and Least Common Multiple

Complete the function solution, which takes two numbers and returns their greatest common divisor and least common multiple. Place the greatest common divisor first in the array, followed by the least common multiple. For example, since the greatest common divisor of 3 and 12 is 3, and their least common multiple is 12, solution(3, 12) should return [3, 12].

• Both numbers are natural numbers between 1 and 1000000, inclusive.

Input/Output Example #1

Same as described above.

Input/Output Example #2

Since the greatest common divisor of the natural numbers 2 and 5 is 1, and their least common multiple is 10, it should return [1, 10].

The problem is to find the greatest common divisor and least common multiple of the two numbers n and m. Once you find the greatest common divisor, you can use n, m, and the greatest common divisor to find the least common multiple.

There's a method of listing out all divisors and comparing them, but you can easily find the greatest common divisor using the Euclidean algorithm.

Euclidean Algorithm

1. Divide n by m to get the remainder r.
   • If r is 0, the divisor at that point is the greatest common divisor.
2. Assign m to n and r to m, then repeat step 1.

Once you've found the greatest common divisor this way, the least common multiple can be found easily.

Multiply n and m, then divide the result by the greatest common divisor.

Build the two resulting values into an array and return it.

JAVA
/**
 * Greatest Common Divisor and Least Common Multiple class
 *
 * @author RWB
 * @since 2021.12.13 Mon 19:33:08
 */
class Solution
{
	/**
	 * Method that returns the answer
	 *
	 * @param n: [int] integer 1
	 * @param m: [int] integer 2
	 *
	 * @return [int[]] answer
	 */
	public int[] solution(int n, int m)
	{
		int[] answer = new int[2];
		
		answer[0] = gcd(n, m);
		answer[1] = n * m / answer[0];
		
		return answer;
	}
	
	/**
	 * Method that returns the result of the Euclidean algorithm
	 *
	 * @param n: [int] integer 1
	 * @param m: [int] integer 2
	 *
	 * @return [int] greatest common divisor
	 */
	private int gcd(int n, int m)
	{
		while (m != 0)
		{
			int r = n % m;
			
			n = m;
			m = r;
		}
		
		return n;
	}
}