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.