GCD and LCM Euclidean Algorithm in DSA Typescript - 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 Euclidean Algorithm used for?

The Euclidean Algorithm is a method to find the GCD of two numbers by repeatedly subtracting the smaller number from the larger one or using the remainder operation until the remainder is zero.

beginner

How do you calculate LCM using GCD?

LCM (Least Common Multiple) of two numbers can be calculated using their GCD with the formula: LCM(a, b) = (a * b) / GCD(a, b).

intermediate

Explain the step-by-step process of the Euclidean Algorithm for GCD of 48 and 18.

1. Divide 48 by 18, remainder is 12.
2. Divide 18 by 12, remainder is 6.
3. Divide 12 by 6, remainder is 0.
4. When remainder is 0, the divisor (6) 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 24 and 36 using the Euclidean Algorithm?

A 12

B 6

C 24

D 18

36 % 24 = 12, 24 % 12 = 0, so GCD is 12.

Which formula correctly calculates LCM from GCD?

A LCM = a + b - GCD

B LCM = GCD / (a * b)

C LCM = (a * b) / GCD

D LCM = a - b + GCD

LCM is calculated as (a * b) divided by their GCD.

In the Euclidean Algorithm, what do you do when the remainder becomes zero?

A Subtract the remainder from divisor

B Continue dividing

C Add the divisor and remainder

D Stop and the divisor is the GCD

When remainder is zero, the divisor at that step is the GCD.

What is the first step in the Euclidean Algorithm for numbers a and b (a > b)?

A Subtract a from b

B Divide a by b and find remainder

C Divide b by a

D Add a and b

You divide the larger number a by smaller number b and find the remainder.

Why is LCM useful in real life?

A To find the smallest common multiple for scheduling or syncing events

B To subtract numbers easily

C To find the largest number dividing two numbers

D To multiply numbers faster

LCM helps find the smallest number that is a multiple of two numbers, useful in scheduling repeating events.

Describe how the Euclidean Algorithm finds the GCD of two numbers.

Think about dividing and using remainders repeatedly.

Explain how to calculate the LCM of two numbers using their GCD.

LCM relates to GCD through multiplication and division.

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 Greatest Common Divisor (GCD)

D. The sum of the two numbers

Solution

1. Step 1: Understand the Euclidean algorithm purpose

   The Euclidean algorithm is a method 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 C

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 TypeScript function signatures correctly defines a function to compute GCD using the Euclidean algorithm?

easy

A. function gcd(a: number, b: number): number

B. function gcd(a: string, b: string): string

C. function gcd(a: number): number

D. function gcd(): void

Solution

1. Step 1: Check parameter types for GCD function

   GCD requires two numbers as input, so parameters must be two numbers.

2. Step 2: Check return type

   The function returns a number representing the GCD, so return type must be number.

3. Final Answer:

   function gcd(a: number, b: number): number -> Option A

4. Quick Check:

   Two number inputs and number output [OK]

Hint: GCD needs two number inputs and returns a number [OK]

Common Mistakes:

• Using string types for numeric operations
• Missing one parameter
• Returning void instead of number

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

function gcd(a: number, b: number): number {
  while (b !== 0) {
    const temp = b;
    b = a % b;
    a = temp;
  }
  return a;
}

console.log(gcd(48, 18));

medium

A. 12

B. 3

C. 18

D. 6

Solution

1. Step 1: Trace the Euclidean algorithm steps for gcd(48, 18)

   48 % 18 = 12, then gcd(18, 12); 18 % 12 = 6, then gcd(12, 6); 12 % 6 = 0, loop ends, gcd is 6.

2. Step 2: Confirm final returned value

   The function returns 6 after the loop ends.

3. Final Answer:

   6 -> Option D

4. Quick Check:

   GCD(48,18) = 6 [OK]

Hint: Use remainder steps until zero remainder [OK]

Common Mistakes:

• Returning the wrong variable after loop
• Confusing modulo operation
• Stopping too early in the loop

4. Identify the error in this TypeScript function for GCD and fix it:

function gcd(a: number, b: number): number {
  while (a !== 0) {
    const temp = a;
    a = b % a;
    b = temp;
  }
  return b;
}

medium

A. Replace '%' with '/' operator in the loop

B. No error, function works correctly

C. Change 'while (a !== 0)' to 'while (b !== 0)' and swap variables accordingly

D. Change 'return b;' to 'return a;' without other changes

Solution

1. Step 1: Test the function with example inputs

   Trace gcd(48, 18): starts a=48 b=18 -> a=18 b=48 -> a=12 b=18 -> a=6 b=12 -> a=0 b=6, returns 6 (correct GCD).

2. Step 2: Verify algorithm correctness

   This is a valid variant of the Euclidean algorithm with swapped roles (gcd(a,b) = gcd(b % a, a)). No syntax/runtime errors, handles edges like gcd(48,0)=48 correctly.

3. Final Answer:

   No error, function works correctly -> Option B

4. Quick Check:

   Equivalent Euclidean variant computes correct GCD [OK]

Hint: Non-standard loop condition but correct GCD computation [OK]

Common Mistakes:

• Assuming loop must check b !== 0
• Proposing to change return to a (breaks it)
• Suggesting / instead of %

5. Given two numbers 24 and 36, which of the following TypeScript code snippets correctly calculates their Least Common Multiple (LCM) using the GCD function?

hard

A. const lcm = (a: number, b: number): number => (a * b) / gcd(a, b);

B. const lcm = (a: number, b: number): number => gcd(a, b) / (a * b);

C. const lcm = (a: number, b: number): number => a + b - gcd(a, b);

D. const lcm = (a: number, b: number): number => Math.max(a, b);

Solution

1. Step 1: Recall the formula relating LCM and GCD

   LCM(a, b) = (a * b) / GCD(a, b). This formula uses the GCD to find the LCM efficiently.

2. Step 2: Check each code snippet against the formula

   const lcm = (a: number, b: number): number => (a * b) / gcd(a, b); matches the formula exactly. Options B, C, and D do not correctly calculate LCM.

3. Final Answer:

   const lcm = (a: number, b: number): number => (a * b) / gcd(a, b); -> Option A

4. Quick Check:

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

Hint: LCM = product divided by GCD [OK]

Common Mistakes:

• Dividing GCD by product instead of product by GCD
• Adding or subtracting instead of dividing
• Using max instead of LCM formula