GCD and LCM Euclidean Algorithm in DSA Java - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of GCD calculation using Euclidean Algorithm

What is the output of the following Java code that calculates the GCD of 48 and 18 using the Euclidean Algorithm?

DSA Java

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

A 6

B 12

C 3

D 9

💡 Hint

Remember the Euclidean Algorithm repeatedly replaces the larger number by the remainder of the division until the remainder is zero.

The GCD of 48 and 18 is 6 because 48 % 18 = 12, then 18 % 12 = 6, then 12 % 6 = 0, so the last non-zero remainder is 6.

❓ Predict Output

intermediate

Output of LCM calculation using GCD

What is the output of the following Java code that calculates the LCM of 15 and 20 using the GCD method?

DSA Java

public class Main {
    public static int gcd(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }
    public static int lcm(int a, int b) {
        return (a / gcd(a, b)) * b;
    }
    public static void main(String[] args) {
        System.out.println(lcm(15, 20));
    }
}

A 100

B 300

C 60

D 35

💡 Hint

LCM can be calculated by dividing the product of the two numbers by their GCD.

GCD of 15 and 20 is 5. LCM = (15 / 5) * 20 = 3 * 20 = 60.

🧠 Conceptual

advanced

Understanding the Euclidean Algorithm steps

Given two numbers 1071 and 462, how many iterations will the Euclidean Algorithm take to find their GCD?

A 3

B 4

C 5

D 6

💡 Hint

Count each step where the remainder is calculated until it reaches zero.

Steps: 1071 % 462 = 147 (1), 462 % 147 = 21 (2), 147 % 21 = 0 (3). Actually, the iterations count the while loop runs: 1) a=1071,b=462 2) a=462,b=147 3) a=147,b=21 4) a=21,b=0 So 4 iterations.

🔧 Debug

advanced

Identify the error in this GCD implementation

What error will the following Java code produce when trying to calculate gcd(10, 0)?

DSA Java

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

A 0

B 10

C ArithmeticException (division by zero)

D StackOverflowError

💡 Hint

Check the base case return value when b is zero.

The base case returns 0 when b == 0, so gcd(10,0) returns 0 incorrectly. The correct base case should return a.

🚀 Application

expert

Find the number of pairs with LCM equal to a given number

Given an integer N = 12, how many pairs of positive integers (a, b) satisfy LCM(a, b) = N?

A 8

B 12

C 10

D 9

💡 Hint

Count pairs (a,b) where both divide N and their LCM is N.

All divisors of 12 are 1,2,3,4,6,12. Pairs (a,b) where LCM(a,b)=12 are counted by checking pairs of divisors whose LCM is 12. There are 9 such pairs.

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