GCD and LCM Euclidean Algorithm in DSA C++

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 smaller ropes without any leftover. LCM is the shortest length where you can line up both ropes end to end evenly.

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 use remainder to reduce the problem size

Step 2: Calculate remainder of 12 divided by 6

12 % 6 = 0

Why: When remainder is zero, divisor is the GCD

Step 3: GCD found as 6, calculate LCM using formula

LCM = (12 * 18) / 6 = 36

Why: LCM is product divided by GCD

Result:

GCD: 6
LCM: 36

Annotated Code

DSA C++

#include <iostream>
using namespace std;

// Function to find GCD using Euclidean Algorithm
int gcd(int a, int b) {
    while (b != 0) {
        int temp = b;          // store current b
        b = a % b;            // remainder replaces b
        a = temp;             // old b becomes new a
    }
    return a;                 // a is GCD when b is zero
}

// Function to find LCM using GCD
int lcm(int a, int b) {
    return (a / gcd(a, b)) * b;  // avoid overflow by dividing first
}

int main() {
    int a = 12, b = 18;
    cout << "GCD: " << gcd(a, b) << "\n";
    cout << "LCM: " << lcm(a, b) << "\n";
    return 0;
}

while (b != 0) {

repeat until remainder is zero

b = a % b;

calculate remainder to reduce problem

a = temp;

shift values to continue Euclidean steps

return a;

return GCD when remainder zero

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

calculate LCM using GCD to avoid overflow

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 regardless of input size

vs Alternative: Naive approach checks all numbers up to min(a,b) which is O(min(a,b)), much slower than Euclidean Algorithm

Edge Cases

One number is zero

GCD is the non-zero number, LCM is zero

DSA C++

while (b != 0) {

Both numbers are equal

GCD is the number itself, LCM is also the number

DSA C++

while (b != 0) {

One number divides the other exactly

GCD is the smaller number, LCM is the larger number

DSA C++

while (b != 0) {

When to Use This Pattern

When you need to find the largest common factor or smallest common multiple quickly, use the Euclidean Algorithm for GCD and derive LCM from it because it is efficient and simple.

Common Mistakes

Mistake: Calculating LCM as (a * b) without dividing by GCD, causing overflow or wrong result
Fix: Always divide by GCD first: LCM = (a / GCD) * b

Mistake: Using recursion without base case or incorrect remainder calculation
Fix: Use iterative loop until remainder is zero to avoid stack overflow

Summary

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

Use when you need to simplify fractions, find common denominators, or solve problems involving divisibility.

The Euclidean Algorithm reduces the problem by replacing numbers with their remainders until zero remainder is found.

Practice

1. What does the Euclidean algorithm primarily calculate between two numbers a and b?

easy

A. The difference between the two numbers

B. The Least Common Multiple (LCM)

C. The sum of the two numbers

D. The Greatest Common Divisor (GCD)

Solution

1. Step 1: Understand the Euclidean algorithm purpose

   The Euclidean algorithm is designed 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. The Euclidean algorithm is for GCD.

3. Final Answer:

   The Greatest Common Divisor (GCD) -> Option D

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

2. Which of the following is the correct syntax for the base case in a recursive Euclidean algorithm function in C++?

easy

A. if (a == b) return 0;

B. if (a == 0) return b;

C. if (b == 0) return a;

D. if (b == a) return b;

Solution

1. Step 1: Identify the base case in Euclidean recursion

   The base case occurs when the second number b becomes zero, then the GCD is the first number a.

2. Step 2: Match the correct syntax

   The correct syntax is if (b == 0) return a; which stops recursion and returns the GCD.

3. Final Answer:

   if (b == 0) return a; -> Option C

4. Quick Check:

   Base case: b == 0 returns a [OK]

Hint: Base case returns a when b is zero [OK]

Common Mistakes:

• Returning 0 instead of a
• Checking if a == b instead of b == 0
• Swapping a and b incorrectly

3. What is the output of the following C++ code snippet?

int gcd(int a, int b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}

int main() {
  std::cout << gcd(48, 18);
  return 0;
}

medium

A. 6

B. 12

C. 18

D. 3

Solution

1. Step 1: Apply Euclidean algorithm steps for gcd(48, 18)

   Calculate gcd(48, 18): 48 % 18 = 12, so next call gcd(18, 12). Then gcd(18, 12): 18 % 12 = 6, next gcd(12, 6). Then gcd(12, 6): 12 % 6 = 0, next gcd(6, 0).

2. Step 2: Reach base case and return result

   When b=0, return a=6. So gcd(48, 18) = 6.

3. Final Answer:

   6 -> Option A

4. Quick Check:

   gcd(48,18) = 6 [OK]

Hint: Use remainder until zero to find GCD [OK]

Common Mistakes:

• Returning 12 instead of 6
• Confusing modulo operation
• Stopping recursion too early

4. Identify the error in this Euclidean algorithm code snippet:

int gcd(int a, int b) {
  if (a == 0) return b;
  return gcd(a % b, b);
}

medium

A. The base case condition is incorrect

B. The recursive call parameters are swapped incorrectly

C. Modulo operator is used wrongly

D. No error, code is correct

Solution

1. Step 1: Check base case correctness

   The base case if (a == 0) return b; is valid because when a is zero, gcd is b.

2. Step 2: Analyze recursive call parameters

   The recursive call uses gcd(a % b, b), but Euclidean algorithm requires gcd(b, a % b). The parameters are swapped incorrectly.

3. Final Answer:

   The recursive call parameters are swapped incorrectly -> Option B

4. Quick Check:

   Correct recursion order: gcd(b, a % b) [OK]

Hint: Always call gcd(b, a % b) in recursion [OK]

Common Mistakes:

• Swapping parameters in recursive call
• Confusing base case condition
• Using modulo with wrong variable

5. Given two positive integers 15 and 20, which of the following expressions correctly calculates their Least Common Multiple (LCM) using the Euclidean algorithm for GCD?

hard

A. LCM = (15 * 20) / gcd(15, 20);

B. LCM = gcd(15, 20) / (15 * 20);

C. LCM = gcd(15, 20) * (15 + 20);

D. LCM = (15 + 20) / gcd(15, 20);

Solution

1. Step 1: Recall the relationship between LCM and GCD

   LCM(a, b) * GCD(a, b) = a * b. So LCM = (a * b) / GCD(a, b).

2. Step 2: Apply formula for 15 and 20

   Calculate gcd(15, 20) = 5, then LCM = (15 * 20) / 5 = 60.

3. Final Answer:

   LCM = (15 * 20) / gcd(15, 20); -> Option A

4. Quick Check:

   LCM * GCD = 15 * 20 [OK]

Hint: LCM = (a*b)/GCD(a,b) always holds [OK]

Common Mistakes:

• Dividing GCD by product instead of product by GCD
• Adding numbers instead of multiplying
• Multiplying GCD by sum instead of dividing