GCD and LCM Euclidean Algorithm in DSA Go - Build from Scratch

GCD and LCM Euclidean Algorithm

📖 Scenario: You are helping a friend who wants to find the greatest common divisor (GCD) and least common multiple (LCM) of two numbers. These are useful in many real-life situations like sharing items equally or scheduling events.

🎯 Goal: Build a Go program that calculates the GCD and LCM of two given numbers using the Euclidean algorithm.

📋 What You'll Learn

Create two integer variables named a and b with exact values 48 and 18

Create a variable originalA and originalB to store the original values of a and b

Use a for loop to implement the Euclidean algorithm to find the GCD of a and b

Calculate the LCM using the formula: (originalA * originalB) / gcd

Print the GCD and LCM in the format: GCD: 6 and LCM: 144

💡 Why This Matters

🌍 Real World

Finding GCD and LCM helps in tasks like dividing items into equal groups, scheduling repeating events, or simplifying fractions.

💼 Career

Understanding algorithms like Euclidean algorithm is fundamental for software developers, especially in fields like cryptography, optimization, and systems programming.

1

Create variables for the two numbers

Create two integer variables called a and b and set them to 48 and 18 respectively.

DSA Go

# Create two integer variables a and b with values 48 and 18
# Your code here

Hint

Use := to declare and assign variables in Go.

2

Store original values for later use

Create two integer variables called originalA and originalB and set them to the current values of a and b.

DSA Go

package main

func main() {
    a := 48
    b := 18
    // Store original values of a and b
    // Your code here
}

Hint

Assign originalA to a and originalB to b.

3

Calculate the GCD using Euclidean algorithm

Use a for loop with the condition b != 0 to repeatedly calculate the remainder of a divided by b. Inside the loop, update a to b and b to the remainder. This will find the GCD stored in a.

DSA Go

package main

func main() {
    a := 48
    b := 18
    originalA := a
    originalB := b
    // Use a for loop to find gcd
    // Your code here
}

Hint

The Euclidean algorithm uses the remainder to find the GCD.

4

Calculate and print the GCD and LCM

Create an integer variable called lcm and set it to the product of originalA and originalB divided by a (the GCD). Then print the GCD and LCM using fmt.Println in the format: GCD: 6 and LCM: 144. Remember to import fmt.

DSA Go

package main

func main() {
    a := 48
    b := 18
    originalA := a
    originalB := b
    for b != 0 {
        remainder := a % b
        a = b
        b = remainder
    }
    // Calculate lcm and print gcd and lcm
    // Your code here
}

Hint

Use fmt.Println("GCD:", a) and fmt.Println("LCM:", lcm) to print results.

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