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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Euclidean GCD function

What is the output of this Python code that calculates the GCD of two numbers using the Euclidean algorithm?

DSA Python

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

print(gcd(48, 18))

A 6

B 12

C 18

D 3

💡 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

Output of LCM calculation using GCD

What is the output of this Python code that calculates the LCM of two numbers using their GCD?

DSA Python

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(15, 20))

A 300

B 35

C 60

D 5

💡 Hint

LCM can be found by multiplying the numbers and dividing by their GCD.

LCM(15, 20) = (15 * 20) / GCD(15, 20). GCD is 5, so LCM = 300 / 5 = 60.

🧠 Conceptual

advanced

Why does the Euclidean algorithm work for GCD?

Which statement best explains why the Euclidean algorithm correctly finds the greatest common divisor (GCD) of two numbers?

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

B Because the algorithm adds the two numbers repeatedly until they become equal, which is the GCD.

C Because it finds the smallest number that divides both numbers without remainder.

D Because it multiplies the two numbers and then divides by their sum to find the GCD.

💡 Hint

Think about how divisors relate to remainders.

The Euclidean algorithm works because the GCD of two numbers also divides their difference or remainder. Replacing the larger number by the remainder keeps the GCD unchanged until the remainder is zero.

❓ Predict Output

advanced

Output of recursive GCD function with negative input

What is the output of this recursive Python function when called with gcd(-24, 18)?

DSA Python

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

print(gcd(-24, 18))

A -6

B 6

C 12

D 0

💡 Hint

The function returns the absolute value of 'a' when 'b' is zero.

The function uses recursion and returns the absolute value of 'a' when 'b' is zero, so the GCD is always positive. The GCD of 24 and 18 is 6.

🧠 Conceptual

expert

Time complexity of Euclidean algorithm for GCD

What is the time complexity of the Euclidean algorithm for finding the GCD of two integers a and b (where a ≥ b > 0)?

A O(1)

B O(b)

C O(a * b)

D O(log b)

💡 Hint

The algorithm reduces the problem size roughly by a factor related to the Fibonacci sequence.

The Euclidean algorithm runs in time proportional to the logarithm of the smaller input number, making it very efficient even for large numbers.

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