GCD and LCM Euclidean Algorithm in DSA Python - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to return the greatest common divisor (GCD) of two numbers using the Euclidean algorithm.

DSA Python

def gcd(a, b):
    while b != 0:
        a, b = b, a [1] b
    return a

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

A%

B+

C-

D*

Attempts:

3 left

💡 Hint

Common Mistakes

Using addition or subtraction instead of the remainder operator.

Using multiplication which does not help find the GCD.

The Euclidean algorithm uses the remainder operator % to find the GCD by repeatedly replacing a with b and b with a % b until b becomes zero.

2fill in blank

medium

Complete the code to calculate the least common multiple (LCM) of two numbers using their GCD.

DSA Python

def lcm(a, b):
    return (a * b) // [1](a, b)

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

Amax

Bmin

Cabs

Dgcd

Attempts:

3 left

💡 Hint

Common Mistakes

Using max or min instead of gcd.

Forgetting to use integer division //.

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

3fill in blank

hard

Fix the error in the recursive GCD function by completing the return statement.

DSA Python

def gcd_recursive(a, b):
    if b == 0:
        return a
    else:
        return gcd_recursive(b, a [1] b)

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

A+

B%

C-

D*

Attempts:

3 left

💡 Hint

Common Mistakes

Using addition or subtraction instead of the remainder operator.

Using multiplication which is incorrect here.

The recursive Euclidean algorithm calls itself with b and the remainder of a % b until b is zero.

4fill in blank

hard

Fill both blanks to create a function that returns a dictionary with GCD and LCM of two numbers.

DSA Python

def gcd_lcm(a, b):
    gcd_value = gcd(a, b)
    lcm_value = (a * b) [1] gcd_value
    return {'gcd': gcd_value, 'lcm': lcm_value}

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

A//

B%

C+

D*

Attempts:

3 left

💡 Hint

Common Mistakes

Using multiplication instead of division for LCM.

Forgetting to close the dictionary properly.

The LCM is calculated by dividing the product of a and b by their GCD using integer division //. The dictionary is closed with a }.

5fill in blank

hard

Fill all three blanks to create a dictionary comprehension that maps numbers to their GCD with a fixed number.

DSA Python

fixed_num = 12
result = [1]: gcd([2], fixed_num) for [3] in range(1, 6)}

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

Anum

Bfixed_num

Ci

Dx

Attempts:

3 left

💡 Hint

Common Mistakes

Using different variable names for key and loop variable.

Using fixed_num as the loop variable.

The dictionary comprehension uses num as the key, calls gcd(num, fixed_num), and iterates over num in the range 1 to 5.

Practice

1. What does the Euclidean algorithm primarily calculate between two numbers?

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 division and remainder operations.

2. Step 2: Differentiate GCD from LCM

   While GCD finds the largest number dividing both inputs, LCM finds the smallest number divisible by both. The Euclidean algorithm is specifically for GCD.

3. Final Answer:

   The greatest common divisor (GCD) -> Option D

4. Quick Check:

   Euclidean algorithm = GCD [OK]

Hint: Euclidean algorithm 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 Python syntax to calculate GCD using the Euclidean algorithm recursively?

easy

A. def gcd(a, b): return a + b if b == 0 else gcd(b, a % b)

B. def gcd(a, b): return a if b == 0 else gcd(b, a % b)

C. def gcd(a, b): while b != 0: a, b = b, a % b return a

D. def gcd(a, b): return b if a == 0 else gcd(a, b % a)

Solution

1. Step 1: Analyze recursive base case and recursive call

   The base case is when b == 0, returning a. Otherwise, call gcd with parameters (b, a % b) to reduce the problem.

2. Step 2: Check each option's correctness

   def gcd(a, b): return a if b == 0 else gcd(b, a % b) matches the correct recursive Euclidean algorithm syntax. def gcd(a, b): return b if a == 0 else gcd(a, b % a) swaps parameters incorrectly. def gcd(a, b): while b != 0: a, b = b, a % b return a is iterative, not recursive. def gcd(a, b): return a + b if b == 0 else gcd(b, a % b) incorrectly adds a and b.

3. Final Answer:

   def gcd(a, b): return a if b == 0 else gcd(b, a % b) -> Option B

4. Quick Check:

   Recursive gcd uses b == 0 base and gcd(b, a % b) call [OK]

Hint: Base case b==0, call gcd(b, a % b) recursively [OK]

Common Mistakes:

• Swapping parameters incorrectly
• Using addition instead of modulo
• Confusing recursive and iterative syntax

3. What is the output of the following Python code?

def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

print(gcd(48, 18))

medium

A. 6

B. 12

C. 18

D. 3

Solution

1. Step 1: Trace the while loop iterations

   Start with a=48, b=18. Iteration 1: a=18, b=48%18=12. Iteration 2: a=12, b=18%12=6. Iteration 3: a=6, b=12%6=0. Loop ends.

2. Step 2: Return the final value of a

   When b=0, return a=6, which is the GCD of 48 and 18.

3. Final Answer:

   6 -> Option A

4. Quick Check:

   GCD(48,18) = 6 [OK]

Hint: Use modulo until remainder zero; last non-zero divisor is GCD [OK]

Common Mistakes:

• Returning b instead of a
• Confusing modulo with division
• Stopping loop too early

4. Find the error in this Python function to compute LCM using GCD:

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

def lcm(a, b):
    return a * b // gcd(a, b)

print(lcm(12, 15))

medium

A. No error; output is correct

B. gcd function has wrong loop condition

C. lcm function should add gcd instead of divide

D. lcm function should use gcd(b, a) instead of gcd(a, b)

Solution

1. Step 1: Check gcd function correctness

   The gcd function uses while b (equivalent to while b != 0), swapping a and b and updating b with a % b. This is correct.

2. Step 2: Verify lcm formula correctness

   LCM is calculated as (a * b) divided by gcd(a, b), which is mathematically correct.

3. Final Answer:

   No error; output is correct -> Option A

4. Quick Check:

   LCM formula = (a*b)//GCD(a,b) [OK]

Hint: LCM = (a*b)//GCD(a,b) is correct formula [OK]

Common Mistakes:

• Using addition instead of division in LCM
• Incorrect loop condition in gcd
• Swapping parameters unnecessarily

5. Given two numbers 21 and 6, use the Euclidean algorithm to find their LCM. What is the correct LCM?

hard

A. 126

B. 18

C. 42

D. 36

Solution

1. Step 1: Calculate GCD of 21 and 6 using Euclidean algorithm

   21 % 6 = 3, then 6 % 3 = 0, so GCD is 3.

2. Step 2: Calculate LCM using formula

   LCM = (21 * 6) // 3 = 126 // 3 = 42.

3. Final Answer:

   42 -> Option C

4. Quick Check:

   LCM = (21*6)//GCD(21,6) = 42 [OK]

Hint: LCM = (a*b)//GCD; find GCD first [OK]

Common Mistakes:

• Calculating LCM as product without dividing by GCD
• Mixing up GCD and LCM values
• Incorrect modulo calculations