GCD and LCM Euclidean Algorithm in DSA C++ - Cheat Sheet & Quick Revision

Recall & Review

beginner

What does GCD stand for and what does it represent?

GCD stands for Greatest Common Divisor. It is the largest number that divides two or more numbers without leaving a remainder.

beginner

What is the main idea behind the Euclidean Algorithm for finding GCD?

The Euclidean Algorithm finds the GCD by repeatedly replacing the larger number with the remainder of dividing the larger by the smaller until the remainder is zero. The last non-zero remainder is the GCD.

intermediate

How is LCM related to GCD for two numbers a and b?

LCM (Least Common Multiple) and GCD are related by the formula: LCM(a, b) = (a * b) / GCD(a, b). This means the product of two numbers equals the product of their GCD and LCM.

beginner

What is the base case in the Euclidean Algorithm for GCD?

The base case occurs when the remainder becomes zero. At this point, the other number is the GCD.

intermediate

Why is the Euclidean Algorithm efficient compared to checking all divisors?

Because it uses division and remainder operations to reduce the problem size quickly, avoiding checking every possible divisor, which saves time especially for large numbers.

What is the GCD of 48 and 18 using the Euclidean Algorithm?

A 18

B 12

C 3

D 6

48 % 18 = 12, 18 % 12 = 6, 12 % 6 = 0, so GCD is 6.

Which step is repeated in the Euclidean Algorithm?

A Subtract smaller number from larger

B Add both numbers

C Divide larger number by smaller and take remainder

D Multiply both numbers

The algorithm repeatedly divides the larger number by the smaller and replaces the larger with the remainder.

If GCD(15, 25) = 5, what is LCM(15, 25)?

A 75

B 50

C 125

D 30

LCM = (15 * 25) / 5 = 375 / 5 = 75.

What happens when the remainder becomes zero in the Euclidean Algorithm?

A Stop and return the other number as GCD

B Continue dividing

C Return zero

D Restart the algorithm

When remainder is zero, the other number is the GCD.

Which of these is NOT true about the Euclidean Algorithm?

A It finds GCD efficiently

B It requires checking all divisors

C It uses division and remainder

D It stops when remainder is zero

The Euclidean Algorithm does NOT check all divisors; it uses division and remainder to find GCD efficiently.

Explain how the Euclidean Algorithm finds the GCD of two numbers step-by-step.

Think about dividing and replacing numbers until you get zero remainder.

Describe the relationship between GCD and LCM and how to calculate LCM using GCD.

Use the product of two numbers and their GCD to find LCM.

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