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.