GCD and LCM Euclidean Algorithm in DSA C# - Execution Trace

Concept Flow - GCD and LCM Euclidean Algorithm

Start with two numbers a, b

↓

Check if b == 0?

Yes→GCD is a

No↓

Calculate a % b

↓

Set a = b, b = a % b

↓

Repeat until b == 0

↓

Calculate LCM = (original_a * original_b) / GCD

Start with two numbers, repeatedly replace a with b and b with a mod b until b is zero. The last non-zero a is the GCD. Then calculate LCM using the formula.

Execution Sample

DSA C#

int a = 48;
int b = 18;
while (b != 0) {
  int temp = b;
  b = a % b;
  a = temp;
}
int gcd = a;
int lcm = (48 * 18) / gcd;

This code finds the GCD of 48 and 18 using Euclid's algorithm, then calculates their LCM.

Execution Table

Step	Operation	a	b	a % b	Pointer Changes	Visual State
1	Start	48	18	N/A	a=48, b=18	a=48, b=18
2	Calculate a % b	48	18	12	temp=18; b=12; a=18	a=18, b=12
3	Calculate a % b	18	12	6	temp=12; b=6; a=12	a=12, b=6
4	Calculate a % b	12	6	0	temp=6; b=0; a=6	a=6, b=0
5	b == 0, stop	6	0	N/A	GCD found: 6	GCD=6
6	Calculate LCM	6	0	N/A	LCM = (48*18)/6 = 144	LCM=144

💡 Loop stops when b becomes 0; last a is GCD.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	Final
a	48	18	12	6	6
b	18	12	6	0	0
temp	N/A	18	12	6	6
gcd	N/A	N/A	N/A	N/A	6
lcm	N/A	N/A	N/A	N/A	144

Key Moments - 3 Insights

Why do we replace a with b and b with a % b in each step?

Because the GCD of two numbers also divides their difference and remainder, so replacing a with b and b with a % b reduces the problem size while keeping the GCD unchanged, as shown in steps 2-4 in the execution_table.

Why does the loop stop when b becomes zero?

When b is zero, the remainder is zero, meaning a divides b exactly. At this point, a holds the GCD, as shown in step 5 where b=0 and GCD=6.

How is LCM calculated after finding GCD?

LCM is calculated using the formula (original_a * original_b) / GCD, ensuring the smallest common multiple. This is shown in step 6 of the execution_table.

Visual Quiz - 3 Questions

Look at the execution_table, what is the value of 'a' after step 3?

A 18

B 12

C 6

D 48

💡 Hint

Check the 'a' column in execution_table row for step 3.

At which step does the variable 'b' become zero?

A Step 4

B Step 5

C Step 2

D Step 3

💡 Hint

Look at the 'b' column in execution_table to find when it reaches 0.

If the initial numbers were 60 and 24, how would the final GCD compare to the one in the table?

A It would be equal to 6

B It would be smaller than 6

C It would be larger than 6

D It would be zero

💡 Hint

Think about the GCD of 60 and 24 compared to 48 and 18.

Concept Snapshot

Euclid's Algorithm for GCD:
- Repeat: a, b = b, a % b until b == 0
- GCD is last non-zero a
- LCM = (original_a * original_b) / GCD
- Efficient and fast for large numbers
- Uses remainder to reduce problem size

Full Transcript

This visualization shows how Euclid's algorithm finds the greatest common divisor (GCD) of two numbers by repeatedly replacing the larger number with the remainder of the division until the remainder is zero. The last non-zero number is the GCD. Then, the least common multiple (LCM) is calculated using the formula (original_a * original_b) divided by the GCD. The execution table traces each step, showing how variables a and b change, and the loop stops when b becomes zero. Key moments clarify why the algorithm works and how LCM is derived. The quiz tests understanding of variable changes and algorithm behavior.

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