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

GCD and LCM using 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 simple C program that calculates the GCD and LCM of two given numbers using the Euclidean Algorithm.

📋 What You'll Learn

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

Create an integer variable original_a to store the original value of a

Use a while loop with condition b != 0 to find the GCD using the Euclidean Algorithm

Calculate the LCM using the formula (original_a * 18) / a

Print the GCD and LCM with the exact format shown

💡 Why This Matters

🌍 Real World

Finding GCD and LCM helps in tasks like dividing items into equal groups or finding common schedules.

💼 Career

Understanding algorithms like Euclidean Algorithm is fundamental for programming jobs that involve problem solving and optimization.

1

Create the initial numbers

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

DSA C

# Your code here

Hint

Use int a = 48; and int b = 18; to create the variables.

2

Save original value of a

Create an integer variable called original_a and set it equal to a to keep the original value for later.

DSA C

int a = 48;
int b = 18;
# Your code here

Hint

Use int original_a = a; to save the original value.

3

Calculate the GCD using Euclidean Algorithm

Use a while loop with the condition b != 0. Inside the loop, create an integer variable temp to store b, then update b to a % b, and finally update a to temp. This will calculate the GCD and store it in a.

DSA C

int a = 48;
int b = 18;
int original_a = a;
# Your code here

Hint

Use the Euclidean Algorithm steps inside the while loop to find the GCD.

4

Calculate and print the GCD and LCM

Create an integer variable lcm and calculate it using the formula (original_a * 18) / a. Then print the GCD and LCM using printf with the exact format:
"GCD: %d\nLCM: %d\n", passing a and lcm respectively.

DSA C

int a = 48;
int b = 18;
int original_a = a;
while (b != 0) {
    int temp = b;
    b = a % b;
    a = temp;
}
# Your code here

Hint

Calculate LCM using the formula and print both values exactly as shown.

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 Greatest Common Divisor (GCD)

D. The sum of the two 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 is the correct syntax for the Euclidean algorithm function header in C to find GCD of two integers a and b?

easy

A. int gcd(int a, int b);

B. void gcd(int a, int b);

C. float gcd(int a, int b);

D. int gcd(float a, float b);

Solution

1. Step 1: Identify return type for GCD function

   GCD is an integer value, so the function should return int.

2. Step 2: Check parameter types

   Parameters a and b should be integers for GCD calculation.

3. Final Answer:

   int gcd(int a, int b); -> Option A

4. Quick Check:

   Function returns int and takes int parameters [OK]

Hint: GCD function returns int and takes int parameters [OK]

Common Mistakes:

• Using void return type for GCD
• Using float parameters or return type
• Missing parameter types

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() {
    printf("%d", gcd(48, 18));
    return 0;
}

medium

A. 12

B. 6

C. 18

D. 3

Solution

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

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

2. Step 2: Return the last non-zero remainder

   When second parameter is 0, return first parameter which is 6.

3. Final Answer:

   6 -> Option B

4. Quick Check:

   GCD(48,18) = 6 [OK]

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

Common Mistakes:

• Returning wrong remainder
• Confusing order of parameters
• Stopping before remainder is zero

4. Identify the error in the following C function to compute LCM using GCD:

int gcd(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

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

medium

A. No error, code is correct

B. GCD function has infinite loop

C. LCM function should use addition instead of multiplication

D. LCM function may cause integer overflow

Solution

1. Step 1: Analyze GCD function correctness

   The GCD function uses Euclidean algorithm correctly with a loop and swapping variables.

2. Step 2: Check LCM calculation for potential issues

   LCM is calculated as (a * b) / gcd(a, b). Multiplying a and b first can cause integer overflow if numbers are large.

3. Final Answer:

   LCM function may cause integer overflow -> Option D

4. Quick Check:

   Multiplying before dividing risks overflow [OK]

Hint: Multiply after dividing by GCD to avoid overflow [OK]

Common Mistakes:

• Assuming no overflow risk
• Thinking GCD function loops infinitely
• Using addition instead of multiplication in LCM

5. Given an array of positive integers arr = {12, 15, 20}, which of the following C code snippets correctly computes the LCM of all elements using the Euclidean algorithm?

hard

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

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

int main() {
int arr[] = {12, 15, 20};
int result = arr[0];
for (int i = 1; i < 3; i++) {
result = lcm(result, arr[i]);
}
printf("%d", result);
return 0;
}

B. int gcd(int a, int b) {
while (b != 0) {
int temp = b;
b = a % b;
a = temp;
}
return a;
}

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

int main() {
int arr[] = {12, 15, 20};
int result = 1;
for (int i = 0; i < 3; i++) {
result = lcm(result, arr[i]);
}
printf("%d", result);
return 0;
}

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

int lcm(int a, int b) {
return a + b - gcd(a, b);
}

int main() {
int arr[] = {12, 15, 20};
int result = arr[0];
for (int i = 1; i < 3; i++) {
result = lcm(result, arr[i]);
}
printf("%d", result);
return 0;
}

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

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

int main() {
int arr[] = {12, 15, 20};
int result = arr[0];
for (int i = 1; i < 3; i++) {
result = lcm(result, arr[i]);
}
printf("%d", result);
return 0;
}

Solution

1. Step 1: Understand LCM calculation in options

   int gcd(int a, int b) {
       if (b == 0) return a;
       return gcd(b, a % b);
   }
   
   int lcm(int a, int b) {
       return (a / gcd(a, b)) * b;
   }
   
   int main() {
       int arr[] = {12, 15, 20};
       int result = arr[0];
       for (int i = 1; i < 3; i++) {
           result = lcm(result, arr[i]);
       }
       printf("%d", result);
       return 0;
   }

   uses lcm(a,b) = (a / gcd(a,b)) * b which avoids overflow and is correct.

   int gcd(int a, int b) {
       while (b != 0) {
           int temp = b;
           b = a % b;
           a = temp;
       }
       return a;
   }
   
   int lcm(int a, int b) {
       return a * b / gcd(a, b);
   }
   
   int main() {
       int arr[] = {12, 15, 20};
       int result = 1;
       for (int i = 0; i < 3; i++) {
           result = lcm(result, arr[i]);
       }
       printf("%d", result);
       return 0;
   }

   starts with result=1 which is valid but risks overflow.

   int gcd(int a, int b) {
       if (b == 0) return a;
       return gcd(b, a % b);
   }
   
   int lcm(int a, int b) {
       return a + b - gcd(a, b);
   }
   
   int main() {
       int arr[] = {12, 15, 20};
       int result = arr[0];
       for (int i = 1; i < 3; i++) {
           result = lcm(result, arr[i]);
       }
       printf("%d", result);
       return 0;
   }

   uses incorrect formula (addition).

   int gcd(int a, int b) {
       if (b == 0) return a;
       return gcd(b, a % b);
   }
   
   int lcm(int a, int b) {
       return (a * b) / gcd(a, b);
   }
   
   int main() {
       int arr[] = {12, 15, 20};
       int result = arr[0];
       for (int i = 1; i < 3; i++) {
           result = lcm(result, arr[i]);
       }
       printf("%d", result);
       return 0;
   }

   uses multiplication first risking overflow.

2. Step 2: Check iteration and initialization

   int gcd(int a, int b) {
       if (b == 0) return a;
       return gcd(b, a % b);
   }
   
   int lcm(int a, int b) {
       return (a / gcd(a, b)) * b;
   }
   
   int main() {
       int arr[] = {12, 15, 20};
       int result = arr[0];
       for (int i = 1; i < 3; i++) {
           result = lcm(result, arr[i]);
       }
       printf("%d", result);
       return 0;
   }

   initializes result with first element and iterates from second element, correctly accumulating LCM. This is the safest and correct approach.

3. Final Answer:

   Option A code snippet correctly computes LCM of all elements -> Option A

4. Quick Check:

   LCM = (a / GCD) * b and accumulate [OK]

Hint: Use (a / gcd) * b to avoid overflow when computing LCM [OK]

Common Mistakes:

• Using addition instead of multiplication for LCM
• Starting with result=1 causing overflow
• Multiplying before dividing causing overflow