GCD and LCM Euclidean Algorithm in DSA Go

Mental Model

GCD finds the biggest number that divides two numbers without leftovers. LCM finds the smallest number both can fit into evenly.

Analogy: Think of two ropes of different lengths. GCD is the longest piece you can cut both ropes into equal parts without waste. LCM is the shortest length where both ropes can be stretched to fit exactly.

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

Dry Run Walkthrough

Input: Find GCD and LCM of 12 and 18

Goal: Calculate the greatest common divisor and least common multiple of 12 and 18 using Euclidean algorithm

Step 1: Calculate remainder of 18 divided by 12

18 % 12 = 6

Why: We replace the bigger number by the remainder to reduce the problem size

Step 2: Calculate remainder of 12 divided by 6

12 % 6 = 0

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

Step 3: GCD is 6; calculate LCM using formula (12 * 18) / 6

LCM = 216 / 6 = 36

Why: LCM is found by dividing product by GCD

Result:

GCD: 6
LCM: 36

Annotated Code

DSA Go

package main

import "fmt"

// gcd calculates the greatest common divisor using Euclidean algorithm
func gcd(a, b int) int {
    for b != 0 {
        a, b = b, a % b // replace a with b, b with remainder
    }
    return a // when b is zero, a is gcd
}

// lcm calculates least common multiple using gcd
func lcm(a, b int) int {
    return (a * b) / gcd(a, b) // product divided by gcd
}

func main() {
    a, b := 12, 18
    fmt.Printf("GCD: %d\n", gcd(a, b))
    fmt.Printf("LCM: %d\n", lcm(a, b))
}

for b != 0 { a, b = b, a % b }

repeat remainder calculation until remainder is zero

return a

return gcd when remainder is zero

return (a * b) / gcd(a, b)

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

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

GCD is the non-zero number, LCM is zero

DSA Go

for b != 0 { a, b = b, a % b }

Both numbers are equal

GCD is the number itself, LCM is the same number

DSA Go

for b != 0 { a, b = b, a % b }

One number divides the other exactly

GCD is the smaller number, LCM is the larger number

DSA Go

for b != 0 { a, b = b, a % b }

When to Use This Pattern

When you need to find the biggest number dividing two numbers or the smallest number both fit into, use Euclidean algorithm for GCD and then calculate LCM from it.

Common Mistakes

Mistake: Using subtraction repeatedly instead of modulo, which is slower
Fix: Use modulo operator to find remainder directly for faster convergence

Mistake: Calculating LCM without dividing by GCD, causing wrong results
Fix: Always divide product of numbers by their GCD to get correct LCM

Summary

Finds the greatest common divisor and least common multiple of two numbers efficiently.

Use when you need to simplify fractions or find common multiples.

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

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