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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of GCD calculation using Euclidean Algorithm

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

DSA C#

using System;
class Program {
    static int GCD(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }
    static void Main() {
        Console.WriteLine(GCD(48, 18));
    }
}

A 18

B 3

C 12

D 6

💡 Hint

Remember the Euclidean Algorithm repeatedly replaces the larger number by the remainder 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 this C# code that calculates the LCM of 15 and 20 using the GCD function?

DSA C#

using System;
class Program {
    static int GCD(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }
    static int LCM(int a, int b) {
        return (a / GCD(a, b)) * b;
    }
    static void Main() {
        Console.WriteLine(LCM(15, 20));
    }
}

A 60

B 300

C 35

D 5

💡 Hint

LCM can be calculated using the formula: LCM(a,b) = (a * b) / GCD(a,b).

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

🧠 Conceptual

advanced

Why does the Euclidean Algorithm work for GCD?

Which of the following best explains why the Euclidean Algorithm correctly finds the GCD of two numbers?

A Because the GCD of two numbers also divides their difference, so repeatedly replacing the larger number by the remainder preserves the GCD.

B Because it adds the two numbers repeatedly until the sum is divisible by both numbers.

C Because the algorithm multiplies the numbers until they become equal, which is the GCD.

D Because it finds the smallest number that divides both numbers without remainder.

💡 Hint

Think about how the remainder relates to the original numbers and their divisors.

The Euclidean Algorithm works because the GCD of two numbers also divides their difference, so replacing the larger number by the remainder does not change the GCD.

🔧 Debug

advanced

Identify the error in this GCD function

What error will occur when running this C# code to compute GCD?

DSA C#

using System;
class Program {
    static int GCD(int a, int b) {
        while (b > 0) {
            int temp = a % b;
            a = b;
            b = temp;
        }
        return a;
    }
    static void Main() {
        Console.WriteLine(GCD(0, 5));
    }
}

A Outputs 0 incorrectly

B Throws DivideByZeroException

C Outputs 5 correctly

D Infinite loop

💡 Hint

Consider what happens when the first argument is zero.

No error occurs. When a=0, b=5 (>0), temp=0%5=0, a=5, b=0, loop ends, returns 5, which is correct GCD(0,5)=5.

🚀 Application

expert

Number of steps in Euclidean Algorithm for GCD(1071, 462)

How many iterations does the Euclidean Algorithm take to compute GCD of 1071 and 462 using the standard while loop?

DSA C#

int GCD(int a, int b) {
    int count = 0;
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
        count++;
    }
    return count;
}
// Call GCD(1071, 462) to get the number of iterations

A 6

B 3

C 5

D 4

💡 Hint

Perform the modulo operations step by step and count how many times the loop runs.

Steps: 1071 % 462 = 147 (1), 462 % 147 = 21 (2), 147 % 21 = 0 (3). Loop runs 3 times, count increments after each iteration, so total 3 iterations.

Practice

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

easy

A. The difference between a and b

B. The Greatest Common Divisor (GCD)

C. The sum of a and b

D. The Least Common Multiple (LCM)

Solution

1. Step 1: Understand the Euclidean algorithm purpose

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

2. Step 2: Differentiate GCD from LCM

   While GCD finds the largest number dividing both, LCM finds the smallest number divisible by both. The Euclidean algorithm directly calculates GCD.

3. Final Answer:

   The Greatest Common Divisor (GCD) -> Option B

4. Quick Check:

   Euclidean algorithm = GCD [OK]

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

Common Mistakes:

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

2. Which of the following is the correct C# syntax to calculate the GCD of two integers a and b using the built-in method?

easy

A. int gcd = Math.GreatestCommonDivisor(a, b);

B. int gcd = Math.GCD(a, b);

C. int gcd = Math.gcd(a, b);

D. int gcd = Math.Gcd(a, b);

Solution

1. Step 1: Identify the correct method name in C#

   The .NET 6+ Math class provides the method Math.Gcd(int, int) to calculate the greatest common divisor.

2. Step 2: Check method name casing and spelling

   Method names in C# are PascalCase, so Math.Gcd is correct, while others are incorrect or do not exist.

3. Final Answer:

   int gcd = Math.Gcd(a, b); -> Option D

4. Quick Check:

   Correct method is Math.Gcd [OK]

Hint: Use Math.Gcd with capital G and C# PascalCase [OK]

Common Mistakes:

• Using incorrect method names like Math.gcd or Math.GCD
• Assuming method is GreatestCommonDivisor
• Wrong casing causing compile errors

3. What is the output of the following C# code?

int a = 48;
int b = 18;
int gcd = Math.Gcd(a, b);
int lcm = (a * b) / gcd;
Console.WriteLine($"GCD: {gcd}, LCM: {lcm}");

medium

A. GCD: 18, LCM: 48

B. GCD: 12, LCM: 72

C. GCD: 6, LCM: 144

D. GCD: 3, LCM: 288

Solution

1. Step 1: Calculate GCD of 48 and 18

   Using Euclidean algorithm: 48 % 18 = 12, 18 % 12 = 6, 12 % 6 = 0, so GCD = 6.

2. Step 2: Calculate LCM using formula

   LCM = (48 * 18) / 6 = 864 / 6 = 144.

3. Final Answer:

   GCD: 6, LCM: 144 -> Option C

4. Quick Check:

   GCD=6, LCM=144 [OK]

Hint: LCM = (a * b) / GCD always [OK]

Common Mistakes:

• Calculating GCD incorrectly
• Swapping GCD and LCM values
• Forgetting to divide product by GCD for LCM

4. Identify the error in this C# code snippet that tries to compute the GCD using Euclidean algorithm:

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

medium

A. Returns b instead of a after loop ends

B. Uses wrong operator for remainder

C. Infinite loop because b never changes

D. Missing base case for zero inputs

Solution

1. Step 1: Trace the Euclidean algorithm loop

   The loop updates a and b until b becomes zero. At loop end, a holds the GCD.

2. Step 2: Check return statement correctness

   The code returns b, which is zero at loop end. It should return a which holds the GCD.

3. Final Answer:

   Returns b instead of a after loop ends -> Option A

4. Quick Check:

   Return a after loop [OK]

Hint: Return 'a' after loop, not 'b' [OK]

Common Mistakes:

• Returning the wrong variable after loop
• Confusing remainder operator with division
• Not updating variables inside loop

5. Given two arrays A = [12, 15, 21] and B = [18, 35, 14], which C# code snippet correctly computes an array of LCMs for each pair (A[i], B[i]) using the Euclidean algorithm?

hard

A. int[] lcms = new int[A.Length];
for (int i = 0; i < A.Length; i++) {
int gcd = Math.Gcd(A[i], B[i]);
lcms[i] = (A[i] * B[i]) / gcd;
}

B. int[] lcms = new int[A.Length];
for (int i = 0; i < A.Length; i++) {
int gcd = Math.Gcd(A[i], B[i]);
lcms[i] = gcd * A[i] * B[i];
}

C. int[] lcms = new int[A.Length];
for (int i = 0; i < A.Length; i++) {
lcms[i] = Math.Gcd(A[i], B[i]);
}

D. int[] lcms = new int[A.Length];
for (int i = 0; i < A.Length; i++) {
lcms[i] = (A[i] + B[i]) / Math.Gcd(A[i], B[i]);
}

Solution

1. Step 1: Calculate GCD for each pair

   Use Math.Gcd(A[i], B[i]) to find the greatest common divisor for each pair.

2. Step 2: Compute LCM using formula

   LCM = (A[i] * B[i]) / GCD. Store this in the lcms array at index i.

3. Final Answer:

   Option A code snippet correctly computes LCM array -> Option A

4. Quick Check:

   LCM = (a*b)/GCD for each pair [OK]

Hint: LCM = (a*b)/GCD for each pair in loop [OK]

Common Mistakes:

• Multiplying GCD with product instead of dividing
• Assigning GCD instead of LCM to result array
• Using sum instead of product in LCM formula