GCD and LCM Euclidean Algorithm in DSA C - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to calculate the GCD of two numbers using the Euclidean algorithm.

DSA C

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

Drag options to blanks, or click blank then click option'

A0

Ba

Ctemp

Db

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'a' instead of 'b' in the modulo operation.

Using 'temp' which is not correct here.

The Euclidean algorithm replaces b with a % b, so the blank must be 'b' to compute the remainder of a divided by b.

2fill in blank

medium

Complete the code to calculate the LCM of two numbers using their GCD.

DSA C

int lcm(int a, int b) {
    return (a * b) / [1](a, b);
}

Drag options to blanks, or click blank then click option'

Alcm

Bgcd

Cmax

Dmin

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'lcm' recursively causing infinite recursion.

Using 'max' or 'min' which are unrelated here.

LCM is calculated by dividing the product of a and b by their GCD, so the blank must be 'gcd'.

3fill in blank

hard

Fix the error in the GCD function to correctly swap values during the Euclidean algorithm.

DSA C

int gcd(int x, int y) {
    while (y != 0) {
        int temp = y;
        y = x [1] y;
        x = temp;
    }
    return x;
}

Drag options to blanks, or click blank then click option'

A%

B/

C*

D+

Attempts:

3 left

💡 Hint

Common Mistakes

Using '/' which gives quotient, not remainder.

Using '+' or '*' which are incorrect here.

The Euclidean algorithm requires taking the remainder of x divided by y, so the operator must be '%'.

4fill in blank

hard

Fill both blanks to complete the function that calculates GCD using recursion.

DSA C

int gcd(int a, int b) {
    if (b == 0) {
        return [1];
    } else {
        return gcd(b, a [2] b);
    }
}

Drag options to blanks, or click blank then click option'

Aa

Bb

C%

D-

Attempts:

3 left

💡 Hint

Common Mistakes

Returning 'b' instead of 'a' in base case.

Using '-' instead of '%' in recursive call.

When b is zero, return a. The recursive call uses modulo operator '%' to find remainder.

5fill in blank

hard

Fill all three blanks to complete the main function that reads two numbers, computes GCD and LCM, and prints them.

DSA C

#include <stdio.h>

int gcd(int a, int b);
int lcm(int a, int b);

int main() {
    int num1, num2;
    scanf("%d %d", &[1], &[2]);
    int gcd_val = gcd(num1, num2);
    int lcm_val = lcm(num1, num2);
    printf("GCD: %d\nLCM: %d\n", [3], lcm_val);
    return 0;
}

Drag options to blanks, or click blank then click option'

Anum1

Bnum2

Cgcd_val

Dlcm_val

Attempts:

3 left

💡 Hint

Common Mistakes

Mixing up variable names in scanf.

Printing num1 or num2 instead of gcd_val.

We read input into num1 and num2, then print gcd_val and lcm_val. The blank in printf for GCD is gcd_val.

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