GCD and LCM Euclidean Algorithm in DSA Go - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of GCD calculation using Euclidean Algorithm

What is the output of this Go code that calculates the GCD of 48 and 18 using the Euclidean Algorithm?

DSA Go

package main
import "fmt"
func gcd(a, b int) int {
    for b != 0 {
        a, b = b, a % b
    }
    return a
}
func main() {
    fmt.Println(gcd(48, 18))
}

A 6

B 12

C 18

D 3

💡 Hint

Remember the Euclidean Algorithm repeatedly replaces the larger number by the remainder until the remainder is zero.

The GCD of 48 and 18 is 6 because 48 % 18 = 12, then 18 % 12 = 6, then 12 % 6 = 0, so the last non-zero remainder is 6.

❓ Predict Output

intermediate

Output of LCM calculation using GCD

What is the output of this Go code that calculates the LCM of 21 and 6 using the GCD function?

DSA Go

package main
import "fmt"
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)
}
func main() {
    fmt.Println(lcm(21, 6))
}

A 42

B 126

C 18

D 36

💡 Hint

LCM can be found by multiplying the numbers and dividing by their GCD.

GCD of 21 and 6 is 3. LCM = (21 * 6) / 3 = 42.

🔧 Debug

advanced

Identify the error in this GCD function implementation

What error does this Go code produce when trying to calculate gcd(10, 0)?

DSA Go

package main
import "fmt"
func gcd(a, b int) int {
    if b == 0 {
        return 0
    }
    return gcd(b, a % b)
}
func main() {
    fmt.Println(gcd(10, 0))
}

A Stack overflow due to infinite recursion

B Runtime panic: division by zero

C Compilation error: missing return statement

D Returns 0 instead of 10

💡 Hint

Check the base case return value when b is zero.

The base case returns 0 when b is zero, but it should return a. So gcd(10,0) returns 0 incorrectly.

🧠 Conceptual

advanced

Number of iterations in Euclidean Algorithm

Given two positive integers a and b (a > b), what is the maximum number of iterations the Euclidean Algorithm takes to find gcd(a, b)?

A Proportional to the sum of a and b

B Proportional to the number of digits in b (log b)

C Always less than 10 iterations

D Equal to the smaller number b

💡 Hint

The Euclidean Algorithm runs in logarithmic time relative to the smaller number.

The number of iterations is proportional to the number of digits (logarithm) of the smaller number b.

🚀 Application

expert

Find the LCM of multiple numbers using GCD

What is the output of this Go code that calculates the LCM of the slice {4, 6, 8} using the GCD function?

DSA Go

package main
import "fmt"
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)
}
func lcmMultiple(nums []int) int {
    result := nums[0]
    for i := 1; i < len(nums); i++ {
        result = lcm(result, nums[i])
    }
    return result
}
func main() {
    fmt.Println(lcmMultiple([]int{4, 6, 8}))
}

A 96

B 12

C 24

D 48

💡 Hint

Calculate LCM pairwise: LCM(4,6)=12, then LCM(12,8)=24.

LCM of 4 and 6 is 12. Then LCM of 12 and 8 is 24. So the final output is 24.

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