GCD and LCM Euclidean Algorithm in DSA Java - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to calculate the GCD of two numbers using the Euclidean algorithm.

DSA Java

public static int gcd(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % [1];
        a = temp;
    }
    return a;
}

Drag options to blanks, or click blank then click option'

Atemp

Ba

Cb

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Using the wrong variable in the modulo operation.

Confusing the order of variables in the modulo.

The Euclidean algorithm replaces b with the remainder of a divided by b, which is a % b. So the blank should be b.

2fill in blank

medium

Complete the code to calculate the LCM of two numbers using their GCD.

DSA Java

public static int lcm(int a, int b) {
    return (a * b) / [1](a, b);
}

Drag options to blanks, or click blank then click option'

Amin

Bgcd

Cmax

Dabs

Attempts:

3 left

💡 Hint

Common Mistakes

Using min or max instead of gcd.

Forgetting to divide by gcd.

The LCM is calculated by dividing the product of the two numbers by their GCD, so the blank should be the gcd function.

3fill in blank

hard

Fix the error in the recursive GCD function by completing the return statement.

DSA Java

public static int gcdRecursive(int a, int b) {
    if (b == 0) {
        return a;
    }
    return gcdRecursive([1], a % b);
}

Drag options to blanks, or click blank then click option'

Ab

Ba

Ca % b

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Using the wrong variable order in the recursive call.

Passing the modulo result as the first argument.

The recursive call swaps the parameters: the first becomes b and the second becomes a % b.

4fill in blank

hard

Fill both blanks to create a method that returns both GCD and LCM as an array.

DSA Java

public static int[] gcdAndLcm(int a, int b) {
    int gcd = [1](a, b);
    int lcm = (a * b) / [2];
    return new int[]{gcd, lcm};
}

Drag options to blanks, or click blank then click option'

Agcd

Blcm

Da

Attempts:

3 left

💡 Hint

Common Mistakes

Using lcm variable before it is defined.

Using wrong variable in LCM calculation.

The first blank calls the gcd function. The second blank uses the gcd variable to calculate LCM.

5fill in blank

hard

Fill all three blanks to create a method that returns a map with keys "GCD" and "LCM" for two numbers.

DSA Java

public static Map<String, Integer> gcdLcmMap(int a, int b) {
    Map<String, Integer> result = new HashMap<>();
    int gcdValue = [1](a, b);
    int lcmValue = (a * b) / [2];
    result.put("GCD", [3]);
    result.put("LCM", lcmValue);
    return result;
}

Drag options to blanks, or click blank then click option'

Agcd

BgcdValue

DlcmValue

Attempts:

3 left

💡 Hint

Common Mistakes

Using undefined variables in map insertion.

Mixing variable names for gcd and lcm.

The method calls gcdValue = gcd(a, b). The LCM divides by gcdValue. The map stores gcdValue for "GCD" key.

Practice

1. What does the Euclidean algorithm primarily calculate between two numbers a and b?

easy

A. The sum of the numbers

B. The Least Common Multiple (LCM)

C. The Greatest Common Divisor (GCD)

D. The difference between the numbers

Solution

1. Step 1: Understand the Euclidean algorithm purpose

   The Euclidean algorithm is designed to find the greatest common divisor (GCD) of two integers by repeatedly applying the remainder operation.

2. Step 2: Differentiate GCD from LCM and others

   While LCM is related to GCD, the Euclidean algorithm directly computes GCD, not LCM or sums/differences.

3. Final Answer:

   The Greatest Common Divisor (GCD) -> Option C

4. Quick Check:

   Euclidean algorithm = GCD [OK]

Hint: Euclidean algorithm finds GCD, not LCM or sums [OK]

Common Mistakes:

• Confusing GCD with LCM
• Thinking it calculates sum or difference
• Assuming it finds prime factors directly

2. Which of the following Java method signatures correctly represents a function to compute the GCD of two integers using the Euclidean algorithm?

easy

A. public static int gcd(int a, int b)

B. public int gcd(int a, int b, int c)

C. static void gcd(int a, int b)

D. public static int gcd()

Solution

1. Step 1: Check method parameters and return type

   The method should take two integers as input and return an integer representing the GCD.

2. Step 2: Validate method signature correctness

   public static int gcd(int a, int b) matches this: it is static, returns int, and takes two int parameters. Others have wrong parameters or return type.

3. Final Answer:

   public static int gcd(int a, int b) -> Option A

4. Quick Check:

   Correct signature = public static int gcd(int a, int b) [OK]

Hint: GCD method needs two int inputs and int return [OK]

Common Mistakes:

• Adding extra parameters unnecessarily
• Using void return type instead of int
• Omitting static keyword when needed

3. What is the output of the following Java code snippet?

public class Test {
  public static int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
  }
  public static void main(String[] args) {
    System.out.println(gcd(48, 18));
  }
}

medium

A. 6

B. 12

C. 18

D. 3

Solution

1. Step 1: Trace gcd(48, 18) calls

   gcd(48,18) calls gcd(18, 48%18=12), then gcd(18,12) calls gcd(12, 18%12=6), then gcd(12,6) calls gcd(6, 12%6=0), returns 6.

2. Step 2: Final return value

   When second parameter is 0, return first parameter which is 6.

3. Final Answer:

   6 -> Option A

4. Quick Check:

   GCD(48,18) = 6 [OK]

Hint: Use remainder until second number is zero [OK]

Common Mistakes:

• Stopping too early without full recursion
• Mixing up modulo operation
• Returning wrong variable when b=0

4. Identify the error in the following Java method for computing LCM using GCD and fix it:

public static int lcm(int a, int b) {
  return a * b / gcd(a, b);
}

public static int gcd(int a, int b) {
  while (b != 0) {
    int temp = a % b;
    a = b;
    b = temp;
  }
  return a;
}

medium

A. Return b instead of a in gcd method

B. gcd method should be static void

C. No error; code is correct

D. Use Math.abs(a * b) to avoid negative LCM

Solution

1. Step 1: Analyze LCM calculation

   LCM is calculated as (a * b) / GCD(a, b). If a or b is negative, product can be negative, causing wrong LCM.

2. Step 2: Fix negative product issue

   Use Math.abs(a * b) to ensure LCM is always positive.

3. Final Answer:

   Use Math.abs(a * b) to avoid negative LCM -> Option D

4. Quick Check:

   LCM must be positive; abs fixes sign [OK]

Hint: Use absolute value for product in LCM formula [OK]

Common Mistakes:

• Ignoring negative inputs causing wrong LCM
• Changing gcd return type incorrectly
• Returning wrong variable in gcd method

5. Given an array of integers nums = {12, 15, 20}, which Java code snippet correctly computes the LCM of all elements using the Euclidean algorithm?

hard

A. int lcm = 1; for(int i=0; i

B. int lcm = nums[0]; for(int i=1; i

C. int lcm = nums[0]; for(int i=1; i

D. int lcm = 0; for(int i=0; i

Solution

1. Step 1: Understand LCM of multiple numbers

   LCM of multiple numbers can be found by iteratively computing LCM of pairs: lcm(a,b,c) = lcm(lcm(a,b), c).

2. Step 2: Check code correctness

   int lcm = nums[0]; for(int i=1; i

3. Final Answer:

   int lcm = nums[0]; for(int i=1; i -> Option B

4. Quick Check:

   Iterative LCM with gcd formula works [OK]

Hint: Iterate LCM pairwise using lcm = (a*b)/gcd(a,b) [OK]

Common Mistakes:

• Using gcd instead of lcm in loop
• Summing elements instead of computing LCM
• Starting lcm from 0 causing division errors