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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Euclidean GCD function

What is the output of this 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);
    std::cout << result << std::endl;
    return 0;
}

A 6

B 12

C 3

D 0

💡 Hint

Remember the Euclidean algorithm repeatedly replaces the larger number by the remainder until the remainder is zero.

The GCD of 48 and 18 is 6 because 6 is the largest number that divides both without remainder. The Euclidean algorithm finds this by repeated modulo operations.

❓ Predict Output

intermediate

LCM calculation using GCD

What is the output of this C++ code that calculates the LCM of 21 and 6 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(21, 6);
    std::cout << result << std::endl;
    return 0;
}

A 42

B 126

C 18

D 12

💡 Hint

LCM can be found by dividing the product of the two numbers by their GCD.

The GCD of 21 and 6 is 3. LCM = (21 / 3) * 6 = 7 * 6 = 42.

🧠 Conceptual

advanced

Why Euclidean Algorithm is efficient for GCD?

Why is the Euclidean algorithm considered efficient for finding the GCD of two numbers?

A It uses addition and subtraction only, avoiding multiplication and division.

B It checks all numbers from 1 to the smaller number to find the greatest divisor.

C It reduces the problem size quickly by replacing the larger number with the remainder, which is smaller.

D It uses recursion without any base case to simplify the problem.

💡 Hint

Think about how the remainder changes in each step.

The Euclidean algorithm reduces the size of the numbers quickly by replacing the larger number with the remainder, which is always smaller, leading to fast convergence.

❓ Predict Output

advanced

Output of recursive GCD function with negative input

What is the output of this C++ code that calculates the GCD of -56 and 98 using a recursive Euclidean algorithm?

DSA C++

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

int main() {
    int result = gcd(-56, 98);
    std::cout << result << std::endl;
    return 0;
}

A 0

B -14

C 42

D 14

💡 Hint

The modulo operator in C++ can return negative values when the dividend is negative.

The recursive function returns the GCD but does not handle negative inputs explicitly, so the result keeps the sign of the first argument, which is -14.

🔧 Debug

expert

Identify the error in this LCM calculation code

What error will this C++ code produce when calculating the LCM of 15 and 20?

DSA 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 result = lcm(15, 20);
    std::cout << result << std::endl;
    return 0;
}

A Logical error producing wrong LCM value

B Runtime error due to integer overflow

C Compilation error due to missing header

D No error, output is 60

💡 Hint

Check if the multiplication a * b can overflow for these inputs.

For inputs 15 and 20, a * b = 300 fits in int range, so no overflow occurs. The output is correct: 60.

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