GCD and LCM Euclidean Algorithm in DSA Typescript - Build from Scratch

GCD and LCM Euclidean Algorithm

📖 Scenario: You are helping a friend who wants to find the greatest common divisor (GCD) and least common multiple (LCM) of two numbers. These are useful in many real-life situations like sharing items evenly or scheduling repeating events.

🎯 Goal: Build a simple program that calculates the GCD and LCM of two given numbers using the Euclidean algorithm.

📋 What You'll Learn

Create two number variables with exact values

Add a helper function to compute GCD using the Euclidean algorithm

Calculate LCM using the GCD

Print the GCD and LCM results

💡 Why This Matters

🌍 Real World

Finding GCD and LCM helps in tasks like dividing items evenly, scheduling events, and simplifying fractions.

💼 Career

Understanding Euclidean algorithm and basic number theory is useful in software development, especially in areas like cryptography, algorithms, and problem solving.

1

Create two number variables

Create two number variables called num1 and num2 with values 48 and 18 respectively.

DSA Typescript

// Create two number variables num1 and num2 with values 48 and 18
// Your code here

Hint

Use const to declare the variables and assign the exact numbers 48 and 18.

2

Write a function to compute GCD using Euclidean algorithm

Write a function called gcd that takes two numbers a and b and returns their greatest common divisor using the Euclidean algorithm.

DSA Typescript

const num1: number = 48;
const num2: number = 18;

// Write function gcd(a: number, b: number): number using Euclidean algorithm
// Your code here

Hint

Use a while loop that runs while b is not zero. Inside, update a and b using the remainder operator %.

3

Calculate LCM using the GCD function

Create a variable called lcm that calculates the least common multiple of num1 and num2 using the formula: (num1 * num2) / gcd(num1, num2).

DSA Typescript

const num1: number = 48;
const num2: number = 18;

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

// Calculate lcm using gcd and assign to variable lcm
// Your code here

Hint

Use the formula for LCM and call the gcd function with num1 and num2.

4

Print the GCD and LCM results

Print the GCD and LCM values using console.log with the exact format:
"GCD: " followed by the GCD value,
and on the next line "LCM: " followed by the LCM value.

DSA Typescript

const num1: number = 48;
const num2: number = 18;

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

const lcm: number = (num1 * num2) / gcd(num1, num2);

// Print GCD and LCM values
// Your code here

Hint

Use console.log twice: once for GCD and once for LCM, with the exact text format.

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