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'

Ab

Btemp

Ca

D0

Attempts:

3 left

💡 Hint

Common Mistakes

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

Using a constant like 0 instead of a variable.

The Euclidean algorithm uses the remainder of a divided by b, so the blank should be 'b' to compute 'a % 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'

Agcd

Bmax

Cmin

Dabs

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'max' or 'min' instead of 'gcd'.

Forgetting to divide by the GCD.

The LCM is calculated by dividing the product of the two numbers by their GCD.

3fill in blank

hard

Fix the error in the recursive GCD function code.

DSA C++

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

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

Aa

Bb

Ca % b

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Swapping the arguments incorrectly.

Using 'a' instead of 'b' as the first argument.

In the recursive call, the first argument should be 'b' and the second 'a % b' to correctly apply the Euclidean algorithm.

4fill in blank

hard

Fill both blanks to create a function that returns a map of numbers to their GCD with a fixed number.

DSA C++

std::map<int, int> gcd_map(const std::vector<int>& nums, int fixed) {
    std::map<int, int> result;
    for (int num : nums) {
        result[num] = gcd([1], [2]);
    }
    return result;
}

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

Afixed

Bnum

Cnums.size()

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Using the size of the vector instead of the current number.

Swapping the order incorrectly.

The gcd function should be called with the current number 'num' and the fixed number 'fixed'.

5fill in blank

hard

Fill both blanks to create a function that returns a map of numbers to their LCM with a fixed number.

DSA C++

std::map<int, int> lcm_map(const std::vector<int>& nums, int fixed) {
    std::map<int, int> result;
    for (int num : nums) {
        result[num] = (num * fixed) / [1](num, [2]);
    }
    return result;
}

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

Amax

Bgcd

Cfixed

Dmin

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'max' or 'min' instead of 'gcd'.

Swapping the order of arguments incorrectly.

The LCM is calculated by dividing the product of 'num' and 'fixed' by their GCD. The function to use is 'gcd', and the second argument is 'fixed'.

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