GCD and LCM Euclidean Algorithm in DSA Go - Execution Trace

Concept Flow - GCD and LCM Euclidean Algorithm

Start with two numbers a and 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 by b and b by a mod b until b is zero. The last non-zero a is the GCD. Then calculate LCM using GCD.

Execution Sample

DSA Go

func gcd(a, b int) int {
  for b != 0 {
    a, b = b, a % b
  }
  return a
}

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

This code finds the GCD of two numbers using the Euclidean algorithm and then calculates the LCM using the GCD.

Execution Table

Step	Operation	a	b	a % b	GCD so far	Visual State
1	Start with a=48, b=18	48	18	N/A	N/A	a=48, b=18
2	Calculate a % b	48	18	12	N/A	48 % 18 = 12
3	Set a=b, b=a%b	18	12	N/A	N/A	a=18, b=12
4	Calculate a % b	18	12	6	N/A	18 % 12 = 6
5	Set a=b, b=a%b	12	6	N/A	N/A	a=12, b=6
6	Calculate a % b	12	6	0	N/A	12 % 6 = 0
7	Set a=b, b=a%b	6	0	N/A	6	a=6, b=0; GCD found
8	Calculate LCM	48	18	N/A	6	LCM = (48*18)/6 = 144
9	End	6	0	N/A	6	GCD=6, LCM=144

💡 Loop ends when b becomes 0; last a is GCD. Then LCM is calculated.

Variable Tracker

Variable	Start	After Step 2	After Step 4	After Step 6	After Step 7	Final
a	48	18	12	6	6	6
b	18	12	6	0	0	0
a % b	N/A	12	6	0	N/A	N/A
GCD so far	N/A	N/A	N/A	N/A	6	6

Key Moments - 3 Insights

Why do we replace a with b and b with a % b instead of other values?

Because the Euclidean algorithm relies on the fact that GCD(a, b) = GCD(b, a % b). This is shown in steps 2, 4, and 6 where a % b is calculated and then used to update b.

Why does the loop stop when b becomes zero?

When b is zero, a holds the GCD. This is shown in step 7 where b=0 and a=6, so the algorithm stops and returns a as the GCD.

How is LCM calculated after finding GCD?

LCM is calculated using the formula LCM = (original_a * original_b) / GCD, as shown in step 8 where 48*18/6 = 144.

Visual Quiz - 3 Questions

Look at the execution table, what is the value of b after step 4?

A 18

B 6

C 12

D 0

💡 Hint

Check the 'b' column in the execution_table row for step 4.

At which step does the condition b == 0 become true, stopping the loop?

A Step 7

B Step 6

C Step 8

D Step 5

💡 Hint

Look at the 'b' column and see when it becomes zero in the execution_table.

If the initial numbers were 30 and 12 instead of 48 and 18, how would the final GCD change?

A It would be 18

B It would be 6

C It would be 12

D It would be 30

💡 Hint

Recall that GCD(30,12) is the largest number dividing both; check variable_tracker logic.

Concept Snapshot

GCD(a,b) uses Euclidean algorithm:
Repeat: a,b = b, a % b until b=0
Last a is GCD.
LCM(a,b) = (a*b)/GCD(a,b).
Efficient for large numbers.
Simple loop with modulo.

Full Transcript

This visualization shows how the Euclidean algorithm finds the greatest common divisor (GCD) of two numbers by repeatedly replacing the pair (a,b) with (b, a mod b) until b becomes zero. The last non-zero a is the GCD. Then the least common multiple (LCM) is calculated using the formula (a*b)/GCD. The execution table traces each step with values of a, b, and their modulo, showing how the algorithm progresses and stops. Key moments clarify why the replacements happen, why the loop stops at b=0, and how LCM is derived. The quiz tests understanding of variable values at specific steps and the effect of changing inputs.

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 a method 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. Euclidean algorithm is for GCD.

3. Final Answer:

   The Greatest Common Divisor (GCD) -> Option C

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 Go code snippets correctly implements the Euclidean algorithm to find the GCD of two integers a and b?

easy

A. func gcd(a, b int) int { if b == 0 { return a } return gcd(b, a % b) }

B. func gcd(a, b int) int { return a + b }

C. func gcd(a, b int) int { for i := 1; i <= a && i <= b; i++ { if a%i == 0 && b%i == 0 { return i } } return 1 }

D. func gcd(a, b int) int { return a * b }

Solution

1. Step 1: Check recursive Euclidean algorithm syntax

   func gcd(a, b int) int { if b == 0 { return a } return gcd(b, a % b) } uses recursion and modulo operation correctly: if b is zero, return a; else call gcd(b, a % b).

2. Step 2: Verify other options for correctness

   func gcd(a, b int) int { return a + b } returns sum, C returns first divisor found (incorrect logic), D returns product. Only A is correct.

3. Final Answer:

   func gcd(a, b int) int { if b == 0 { return a } return gcd(b, a % b) } -> Option A

4. Quick Check:

   Correct recursive gcd code = func gcd(a, b int) int { if b == 0 { return a } return gcd(b, a % b) } [OK]

Hint: Use recursion with modulo for Euclidean GCD [OK]

Common Mistakes:

• Returning sum or product instead of GCD
• Incorrect loop logic for GCD
• Missing base case for recursion

3. What is the output of the following Go code?

package main
import "fmt"
func gcd(a, b int) int {
 if b == 0 {
  return a
 }
 return gcd(b, a % b)
}
func lcm(a, b int) int {
 return (a * b) / gcd(a, b)
}
func main() {
 fmt.Println(gcd(12, 18))
 fmt.Println(lcm(12, 18))
}

medium

A. 6
36

B. 3
72

C. 6
54

D. 12
18

Solution

1. Step 1: Calculate gcd(12, 18) using Euclidean algorithm

   18 % 12 = 6, gcd(12, 6) -> 12 % 6 = 0, gcd(6, 0) = 6. So gcd is 6.

2. Step 2: Calculate lcm(12, 18) using formula

   LCM = (12 * 18) / 6 = 216 / 6 = 36.

3. Final Answer:

   6 36 -> Option A

4. Quick Check:

   GCD=6, LCM=36 [OK]

Hint: LCM = (a*b)/GCD; find GCD first [OK]

Common Mistakes:

• Mixing up GCD and LCM values
• Incorrect modulo calculations
• Forgetting integer division

4. Identify the bug in this Go function intended to compute the GCD using the Euclidean algorithm:

func gcd(a, b int) int {
 for b != 0 {
  a = b
  b = a % b
 }
 return a
}

medium

A. The function should return b instead of a

B. The loop condition should be a != 0 instead of b != 0

C. The function is correct and has no bugs

D. The order of assignments causes incorrect modulo calculation

Solution

1. Step 1: Analyze the assignment order inside the loop

   Assigning a = b first changes a before calculating b = a % b, so a % b uses updated a, causing wrong result.

2. Step 2: Correct approach for Euclidean algorithm

   Store a % b in a temp variable before updating a, or swap assignments to avoid overwriting needed values.

3. Final Answer:

   The order of assignments causes incorrect modulo calculation -> Option D

4. Quick Check:

   Assignment order matters in Euclidean GCD [OK]

Hint: Update b before a to keep correct modulo values [OK]

Common Mistakes:

• Overwriting variables before modulo calculation
• Wrong loop condition
• Returning wrong variable

5. Given two positive integers a and b, which of the following Go functions correctly computes the LCM using the Euclidean algorithm for GCD, handling the edge case when either a or b is zero?

hard

A. func lcm(a, b int) int { if a == 0 || b == 0 { return 1 } return (a * b) / gcd(a, b) }

B. func lcm(a, b int) int { if a == 0 || b == 0 { return 0 } return (a * b) / gcd(a, b) }

C. func lcm(a, b int) int { if a == 0 && b == 0 { return 1 } return (a + b) / gcd(a, b) }

D. func lcm(a, b int) int { return (a * b) / gcd(a, b) }

Solution

1. Step 1: Understand LCM edge cases

   If either a or b is zero, LCM should be zero because zero times any number is zero.

2. Step 2: Check each option for correct edge handling

   func lcm(a, b int) int { if a == 0 || b == 0 { return 0 } return (a * b) / gcd(a, b) } returns 0 if either input is zero, then calculates LCM correctly. func lcm(a, b int) int { return (a * b) / gcd(a, b) } misses zero check. func lcm(a, b int) int { if a == 0 && b == 0 { return 1 } return (a + b) / gcd(a, b) } returns 1 incorrectly. func lcm(a, b int) int { if a == 0 || b == 0 { return 1 } return (a * b) / gcd(a, b) } returns 1 for zero inputs, which is wrong.

3. Final Answer:

   func lcm(a, b int) int { if a == 0 || b == 0 { return 0 } return (a * b) / gcd(a, b) } -> Option B

4. Quick Check:

   LCM zero if any input zero [OK]

Hint: LCM is zero if either number is zero [OK]

Common Mistakes:

• Ignoring zero inputs in LCM calculation
• Returning 1 instead of 0 for zero inputs
• Using addition instead of multiplication