GCD and LCM Euclidean Algorithm in DSA Go - Time & Space Complexity

Time Complexity: GCD and LCM Euclidean Algorithm

O(log min(a, b))

Understanding Time Complexity

We want to understand how fast the Euclidean algorithm finds the greatest common divisor (GCD) of two numbers.

This helps us know how the steps grow when numbers get bigger.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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

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

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

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The loop repeatedly replaces numbers with their remainder until the remainder is zero.
• How many times: The loop runs as many times as needed to reduce the smaller number to zero by taking remainders.

How Execution Grows With Input

Each step reduces the numbers significantly, so the number of steps grows slowly even if numbers get very large.

Input Size (n)	Approx. Operations
10	About 5 steps
100	About 7 steps
1000	About 10 steps

Pattern observation: The steps grow roughly proportional to the number of digits, not the number size itself.

Final Time Complexity

Time Complexity: O(log min(a, b))

This means the time to find the GCD grows slowly, roughly with the number of digits of the smaller input.

Common Mistake

[X] Wrong: "The Euclidean algorithm takes as many steps as the size of the numbers themselves."

[OK] Correct: Each step reduces the problem size quickly by using remainders, so it takes far fewer steps than the number size.

Interview Connect

Understanding this algorithm's time complexity shows you can analyze efficient number operations, a useful skill in many coding problems.

Self-Check

"What if we used subtraction instead of remainder in the loop? How would the time complexity change?"

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