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↓

Compute 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 the larger by remainder until zero remainder; last non-zero is GCD. Then use GCD to find LCM.

Execution Sample

DSA C++

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

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

This code finds GCD using Euclid's method and then calculates LCM using the GCD.

Execution Table

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

💡 Loop ends when b becomes 0; last a is GCD; LCM calculated using 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	-	18	12	6	-

Key Moments - 3 Insights

Why do we swap a and b using temp before updating b?

Because in the Euclidean algorithm, the new a becomes the old b, and b becomes the remainder a % b. Using temp stores old b so we don't lose it before updating.

Why does the loop stop when b becomes zero?

Because when b is zero, the remainder is zero, meaning a divides b exactly. The current a is the greatest common divisor (GCD). This is shown in step 5 of the execution_table.

How is LCM calculated from GCD?

LCM is calculated by multiplying the original two numbers and dividing by their 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 6

B 18

C 12

D 48

💡 Hint

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

At which step does the variable 'b' become zero, ending the loop?

A Step 4

B Step 2

C Step 3

D Step 5

💡 Hint

Look at the 'b' column in execution_table and find when it first becomes 0.

If the initial numbers were 30 and 12, how would the final GCD in the execution_table change?

A It would be 18

B It would be 6

C It would be 12

D It would be 30

💡 Hint

Recall GCD of 30 and 12 is 6; compare with the original example's GCD.

Concept Snapshot

Euclidean Algorithm for GCD:
- Repeat: a % b, then a=b, b=remainder
- Stop when b=0; a is GCD
LCM = (a_original * b_original) / GCD
Efficient for large numbers
Simple loop with remainder operation

Full Transcript

The Euclidean Algorithm finds the greatest common divisor (GCD) of two numbers by repeatedly replacing the larger number with the remainder of dividing the larger by the smaller. This continues until the remainder is zero, at which point the other number is the GCD. The least common multiple (LCM) is then calculated by dividing the product of the original numbers by the GCD. The code uses a loop to update variables a and b, swapping and computing remainders until b is zero. The final GCD and LCM are then returned.

Practice

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

easy

A. The difference between the two numbers

B. The Least Common Multiple (LCM)

C. The sum of the two numbers

D. The Greatest Common Divisor (GCD)

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

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

3. Final Answer:

   The Greatest Common Divisor (GCD) -> Option D

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

2. Which of the following is the correct syntax for the base case in a recursive Euclidean algorithm function in C++?

easy

A. if (a == b) return 0;

B. if (a == 0) return b;

C. if (b == 0) return a;

D. if (b == a) return b;

Solution

1. Step 1: Identify the base case in Euclidean recursion

   The base case occurs when the second number b becomes zero, then the GCD is the first number a.

2. Step 2: Match the correct syntax

   The correct syntax is if (b == 0) return a; which stops recursion and returns the GCD.

3. Final Answer:

   if (b == 0) return a; -> Option C

4. Quick Check:

   Base case: b == 0 returns a [OK]

Hint: Base case returns a when b is zero [OK]

Common Mistakes:

• Returning 0 instead of a
• Checking if a == b instead of b == 0
• Swapping a and b incorrectly

3. What is the output of the following C++ code snippet?

int gcd(int a, int b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}

int main() {
  std::cout << gcd(48, 18);
  return 0;
}

medium

A. 6

B. 12

C. 18

D. 3

Solution

1. Step 1: Apply Euclidean algorithm steps for gcd(48, 18)

   Calculate gcd(48, 18): 48 % 18 = 12, so next call gcd(18, 12). Then gcd(18, 12): 18 % 12 = 6, next gcd(12, 6). Then gcd(12, 6): 12 % 6 = 0, next gcd(6, 0).

2. Step 2: Reach base case and return result

   When b=0, return a=6. So gcd(48, 18) = 6.

3. Final Answer:

   6 -> Option A

4. Quick Check:

   gcd(48,18) = 6 [OK]

Hint: Use remainder until zero to find GCD [OK]

Common Mistakes:

• Returning 12 instead of 6
• Confusing modulo operation
• Stopping recursion too early

4. Identify the error in this Euclidean algorithm code snippet:

int gcd(int a, int b) {
  if (a == 0) return b;
  return gcd(a % b, b);
}

medium

A. The base case condition is incorrect

B. The recursive call parameters are swapped incorrectly

C. Modulo operator is used wrongly

D. No error, code is correct

Solution

1. Step 1: Check base case correctness

   The base case if (a == 0) return b; is valid because when a is zero, gcd is b.

2. Step 2: Analyze recursive call parameters

   The recursive call uses gcd(a % b, b), but Euclidean algorithm requires gcd(b, a % b). The parameters are swapped incorrectly.

3. Final Answer:

   The recursive call parameters are swapped incorrectly -> Option B

4. Quick Check:

   Correct recursion order: gcd(b, a % b) [OK]

Hint: Always call gcd(b, a % b) in recursion [OK]

Common Mistakes:

• Swapping parameters in recursive call
• Confusing base case condition
• Using modulo with wrong variable

5. Given two positive integers 15 and 20, which of the following expressions correctly calculates their Least Common Multiple (LCM) using the Euclidean algorithm for GCD?

hard

A. LCM = (15 * 20) / gcd(15, 20);

B. LCM = gcd(15, 20) / (15 * 20);

C. LCM = gcd(15, 20) * (15 + 20);

D. LCM = (15 + 20) / gcd(15, 20);

Solution

1. Step 1: Recall the relationship between LCM and GCD

   LCM(a, b) * GCD(a, b) = a * b. So LCM = (a * b) / GCD(a, b).

2. Step 2: Apply formula for 15 and 20

   Calculate gcd(15, 20) = 5, then LCM = (15 * 20) / 5 = 60.

3. Final Answer:

   LCM = (15 * 20) / gcd(15, 20); -> Option A

4. Quick Check:

   LCM * GCD = 15 * 20 [OK]

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

Common Mistakes:

• Dividing GCD by product instead of product by GCD
• Adding numbers instead of multiplying
• Multiplying GCD by sum instead of dividing