GCD and LCM Euclidean Algorithm in DSA C#

Mental Model

GCD is the biggest number that divides two numbers without leaving a remainder. LCM is the smallest number that both numbers can divide into evenly.

Analogy: Think of two ropes of different lengths. GCD is the longest length you can cut both ropes into equal pieces without leftover. LCM is the shortest length of a new rope that can be made by joining whole pieces of both ropes.

Number A: 12
Number B: 18
GCD: ?
LCM: ?

Dry Run Walkthrough

Input: Find GCD and LCM of 12 and 18 using Euclidean Algorithm

Goal: Calculate the greatest common divisor (GCD) and least common multiple (LCM) of 12 and 18

Step 1: Calculate remainder of 18 divided by 12

18 % 12 = 6

Why: We use remainder to reduce the problem size

Step 2: Replace 18 with 12, and 12 with remainder 6

Now find GCD of 12 and 6

Why: Euclidean algorithm reduces the problem step by step

Step 3: Calculate remainder of 12 divided by 6

12 % 6 = 0

Why: When remainder is zero, the divisor is the GCD

Step 4: GCD is 6

GCD(12,18) = 6

Why: Last non-zero divisor is the greatest common divisor

Step 5: Calculate LCM using formula: (12 * 18) / 6

LCM = 36

Why: LCM is product divided by GCD

Result:

GCD: 6
LCM: 36

Annotated Code

DSA C#

using System;

class GcdLcmCalculator
{
    // Calculate GCD using Euclidean Algorithm
    public static int GCD(int a, int b)
    {
        while (b != 0)
        {
            int remainder = a % b; // find remainder
            a = b;                // move b to a
            b = remainder;        // move remainder to b
        }
        return a; // a is gcd when b is zero
    }

    // Calculate LCM using GCD
    public static int LCM(int a, int b)
    {
        return (a / GCD(a, b)) * b; // avoid overflow by dividing first
    }

    static void Main()
    {
        int num1 = 12;
        int num2 = 18;

        int gcd = GCD(num1, num2);
        int lcm = LCM(num1, num2);

        Console.WriteLine($"GCD: {gcd}");
        Console.WriteLine($"LCM: {lcm}");
    }
}

while (b != 0)

repeat until remainder is zero

int remainder = a % b; // find remainder

calculate remainder of a divided by b

a = b; // move b to a

shift b to a for next iteration

b = remainder; // move remainder to b

shift remainder to b for next iteration

return a; // a is gcd when b is zero

return gcd when remainder is zero

return (a / GCD(a, b)) * b; // avoid overflow by dividing first

calculate lcm using gcd

Output

GCD: 6

LCM: 36

Complexity Analysis

Time: O(log(min(a, b))) because each step reduces the problem size by remainder

Space: O(1) because only a few variables are used regardless of input size

vs Alternative: Euclidean algorithm is much faster than checking all divisors up to min(a,b), which is O(min(a,b))

Edge Cases

One number is zero, e.g. GCD(0, 5)

GCD returns the non-zero number, LCM is zero

DSA C#

while (b != 0)

Both numbers are equal, e.g. GCD(7, 7)

GCD returns the number itself, LCM is the same number

DSA C#

while (b != 0)

One number divides the other exactly, e.g. GCD(4, 12)

GCD returns the smaller number, LCM is the larger number

DSA C#

while (b != 0)

When to Use This Pattern

When you need to find the greatest common divisor or least common multiple efficiently, use the Euclidean algorithm because it quickly reduces the problem using remainders.

Common Mistakes

Mistake: Using addition or subtraction repeatedly instead of modulo for GCD
Fix: Use the modulo operator (%) to find remainder for faster convergence

Mistake: Calculating LCM as a * b without dividing by GCD first, causing overflow
Fix: Calculate LCM as (a / GCD(a,b)) * b to reduce risk of overflow

Summary

Calculates the greatest common divisor and least common multiple of two numbers using the Euclidean algorithm.

Use when you need fast and reliable GCD or LCM calculations for integers.

The key insight is that GCD can be found by repeatedly replacing the larger number with the remainder until zero.

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