GCD and LCM Euclidean Algorithm in DSA C - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of GCD calculation using Euclidean Algorithm

What is the output of the following C code that calculates the GCD of 48 and 18 using the Euclidean Algorithm?

DSA C

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

int main() {
    int result = gcd(48, 18);
    printf("%d\n", result);
    return 0;
}

A 9

B 12

C 3

D 6

💡 Hint

Remember the Euclidean Algorithm repeatedly replaces the larger number by the remainder of the division until the remainder is zero.

The GCD of 48 and 18 is 6 because 48 % 18 = 12, then 18 % 12 = 6, then 12 % 6 = 0, so the last non-zero remainder is 6.

❓ Predict Output

intermediate

Output of LCM calculation using GCD

What is the output of the following C code that calculates the LCM of 15 and 20 using the GCD function?

DSA C

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 / gcd(a, b)) * b;
}

int main() {
    int result = lcm(15, 20);
    printf("%d\n", result);
    return 0;
}

A 100

B 60

C 35

D 300

💡 Hint

LCM can be calculated using the formula: LCM(a,b) = (a * b) / GCD(a,b).

GCD of 15 and 20 is 5. So LCM = (15 / 5) * 20 = 3 * 20 = 60.

🧠 Conceptual

advanced

Why does the Euclidean Algorithm work for GCD?

Which of the following best explains why the Euclidean Algorithm correctly computes the GCD of two numbers?

A Because the algorithm multiplies the two numbers until they become equal, which is the GCD.

B Because it adds the two numbers repeatedly until the sum is divisible by both numbers.

C Because the GCD of two numbers also divides their difference, so repeatedly replacing the larger number by the remainder preserves the GCD.

D Because it finds the smallest number that divides both numbers by checking all numbers from 1 upwards.

💡 Hint

Think about how divisors relate to remainders.

The Euclidean Algorithm works because the GCD of two numbers also divides their difference and remainder, so replacing the larger number by the remainder keeps the GCD unchanged until the remainder is zero.

🔧 Debug

advanced

Identify the error in this GCD function implementation

What error will occur when running this C code to compute GCD?

DSA C

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

int main() {
    int result = gcd(48, 18);
    printf("%d\n", result);
    return 0;
}

A No error; output is 6

B Runtime error: division by zero

C Infinite loop

D Compilation error

💡 Hint

Check the loop condition and the order of variables in the modulo operation.

No error occurs. This is a valid implementation of the Euclidean algorithm with the roles of a and b swapped compared to the standard version. It correctly outputs 6.

🚀 Application

expert

Number of steps in Euclidean Algorithm for GCD(1071, 462)

How many iterations does the Euclidean Algorithm take to compute GCD of 1071 and 462 using the standard while loop method?

DSA C

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

int main() {
    int steps = gcd(1071, 462);
    printf("%d\n", steps);
    return 0;
}

A 3

B 4

C 5

D 6

💡 Hint

Perform the Euclidean Algorithm step by step counting each iteration.

Steps: 1) 1071 % 462 = 147 2) 462 % 147 = 21 3) 147 % 21 = 0 The loop executes 3 times, incrementing count to 3.