GCD and LCM Euclidean Algorithm in DSA Typescript

Mental Model

GCD finds the biggest number that divides two numbers without leftovers. LCM finds the smallest number both can fit into evenly.

Analogy: Think of two ropes of different lengths. GCD is the longest piece you can cut both ropes into equal smaller ropes without leftover. LCM is the shortest length where you can place both ropes end to end without cutting.

Number A: 12
Number B: 18
GCD: 6 (largest common piece)
LCM: 36 (smallest common multiple)

12 -> |---|---|---|---|---|---| (6 units each)
18 -> |---|---|---|---|---|---|---|---|---| (6 units each)
LCM -> 36 units total length

Dry Run Walkthrough

Input: Find GCD and LCM of 12 and 18

Goal: Calculate the greatest common divisor and least common multiple of 12 and 18 using Euclidean algorithm

Step 1: Calculate remainder of 18 divided by 12

18 % 12 = 6

Why: We use remainder to reduce the problem size

Step 2: Calculate remainder of 12 divided by 6

12 % 6 = 0

Why: When remainder is zero, divisor is GCD

Step 3: GCD found as 6

GCD = 6

Why: No remainder means current divisor divides both numbers exactly

Step 4: Calculate LCM using formula: (12 * 18) / 6

LCM = 36

Why: LCM is product divided by GCD

Result:

GCD = 6
LCM = 36

Annotated Code

DSA Typescript

class Euclidean {
  static gcd(a: number, b: number): number {
    while (b !== 0) {
      const remainder = a % b; // find remainder
      a = b; // move b to a
      b = remainder; // move remainder to b
    }
    return a; // a is gcd when b is zero
  }

  static lcm(a: number, b: number): number {
    return (a * b) / Euclidean.gcd(a, b); // lcm formula
  }
}

// Driver code
const a = 12;
const b = 18;
const gcd = Euclidean.gcd(a, b);
const lcm = Euclidean.lcm(a, b);
console.log(`GCD = ${gcd}`);
console.log(`LCM = ${lcm}`);

while (b !== 0) {

repeat until remainder is zero to find gcd

const remainder = a % b; // find remainder

calculate remainder of a divided by b

a = b; // move b to a

shift b to a for next iteration

b = remainder; // move remainder to b

shift remainder to b for next iteration

return a; // a is gcd when b is zero

return gcd when remainder is zero

return (a * b) / Euclidean.gcd(a, b); // lcm formula

calculate lcm using gcd

Output

GCD = 6

LCM = 36

Complexity Analysis

Time: O(log(min(a, b))) because each step reduces the problem size by remainder

Space: O(1) because only a few variables are used regardless of input size

vs Alternative: Euclidean algorithm is much faster than checking all divisors up to min(a,b), which is O(min(a,b))

Edge Cases

One number is zero, e.g. gcd(0, 5)

GCD is the non-zero number, LCM is zero

DSA Typescript

while (b !== 0) {

Both numbers are equal, e.g. gcd(7, 7)

GCD is the number itself, LCM is the same number

DSA Typescript

while (b !== 0) {

One number divides the other exactly, e.g. gcd(4, 12)

GCD is the smaller number, LCM is the larger number

DSA Typescript

while (b !== 0) {

When to Use This Pattern

When you need to find the greatest common divisor or least common multiple efficiently, reach for the Euclidean algorithm because it uses division and remainder to quickly reduce the problem.

Common Mistakes

Mistake: Stopping the algorithm too early before remainder reaches zero
Fix: Continue the loop until remainder is exactly zero to get correct gcd

Mistake: Calculating LCM without dividing by GCD, causing wrong large number
Fix: Always divide product of numbers by gcd to get correct lcm

Summary

Finds the greatest common divisor and least common multiple of two numbers using division and remainder.

Use when you need fast calculation of gcd or lcm without checking all divisors.

The key insight is that gcd can be found by repeatedly replacing the larger number by the remainder until zero.

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