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

GCD and LCM using Euclidean Algorithm

📖 Scenario: Imagine 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 equally or finding common timings.

🎯 Goal: You will write a small program in JavaScript that calculates the GCD and LCM of two given numbers using the Euclidean algorithm.

📋 What You'll Learn

Create two variables named num1 and num2 with exact values 48 and 18

Create a variable gcd to store the greatest common divisor

Write a function called calculateGCD that uses the Euclidean algorithm to find the GCD of two numbers

Calculate the LCM using the formula (num1 * num2) / gcd and store it in a variable lcm

Print the values of gcd and lcm exactly as shown

💡 Why This Matters

🌍 Real World

Finding GCD and LCM helps in tasks like dividing items into equal groups or scheduling events that repeat over different intervals.

💼 Career

Understanding algorithms like Euclidean GCD is fundamental for software developers, especially in fields like cryptography, optimization, and systems programming.

1

Create the two numbers

Create two variables called num1 and num2 and set them to 48 and 18 respectively.

DSA Javascript

# Your code here

Hint

Use const to create variables and assign the exact numbers.

2

Create a variable to hold the GCD

Create a variable called gcd and set it to 0 to hold the greatest common divisor.

DSA Javascript

const num1 = 48;
const num2 = 18;
# Your code here

Hint

Use let because gcd will change later.

3

Write the Euclidean algorithm function

Write a function called calculateGCD that takes two parameters a and b and returns their greatest common divisor using the Euclidean algorithm. Then set gcd to the result of calling calculateGCD(num1, num2). Also create a variable lcm and set it to (num1 * num2) / gcd.

DSA Javascript

const num1 = 48;
const num2 = 18;
let gcd = 0;
# Your code here

Hint

Use a while loop to repeat until b is zero. Swap values using a temporary variable.

4

Print the GCD and LCM

Print the values of gcd and lcm using console.log exactly as shown: GCD: 6 and LCM: 144.

DSA Javascript

const num1 = 48;
const num2 = 18;
let gcd = 0;

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

gcd = calculateGCD(num1, num2);
const lcm = (num1 * num2) / gcd;
# Your code here

Hint

Use console.log to print the text and values exactly as shown.

Practice

1. What does the Euclidean algorithm primarily calculate when given two positive integers a and b?

easy

A. The difference between a and b

B. The least common multiple (LCM) of a and b

C. The sum of a and b

D. The greatest common divisor (GCD) of a and b

Solution

1. Step 1: Understand the Euclidean algorithm purpose

   The Euclidean algorithm is a method to find the greatest common divisor (GCD) of two numbers 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. Euclidean algorithm is for GCD.

3. Final Answer:

   The greatest common divisor (GCD) of a and b -> 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 directly

2. Which of the following JavaScript function definitions correctly implements the Euclidean algorithm to find the GCD of two numbers a and b?

easy

A. function gcd(a, b) { return a + b; }

B. function gcd(a, b) { while(b !== 0) { let temp = b; b = a % b; a = temp; } return a; }

C. function gcd(a, b) { return Math.min(a, b); }

D. function gcd(a, b) { while(a !== 0) { a = b % a; b = a; } return b; }

Solution

1. Step 1: Analyze the correct Euclidean algorithm loop

   function gcd(a, b) { while(b !== 0) { let temp = b; b = a % b; a = temp; } return a; } uses a while loop that continues until b is zero, swapping values and using modulo to find remainder, which matches the Euclidean algorithm.

2. Step 2: Check other options for correctness

   function gcd(a, b) { return a + b; } returns sum, not GCD. function gcd(a, b) { return Math.min(a, b); } returns minimum, not GCD. function gcd(a, b) { while(a !== 0) { a = b % a; b = a; } return b; } has incorrect variable updates causing infinite loop or wrong result.

3. Final Answer:

   function gcd(a, b) { while(b !== 0) { let temp = b; b = a % b; a = temp; } return a; } -> Option B

4. Quick Check:

   Correct Euclidean loop = function gcd(a, b) { while(b !== 0) { let temp = b; b = a % b; a = temp; } return a; } [OK]

Hint: Use while loop with modulo and swap variables [OK]

Common Mistakes:

• Returning sum or min instead of GCD
• Incorrect variable swapping causing infinite loops
• Using wrong loop conditions

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

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

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

medium

A. 3

B. 12

C. 6

D. 18

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, then gcd(6, 0) = 6.

2. Step 2: Return the last non-zero remainder

   When second number becomes zero, the first number is the GCD, which is 6 here.

3. Final Answer:

   6 -> Option C

4. Quick Check:

   GCD(48,18) = 6 [OK]

Hint: Apply modulo repeatedly until remainder is zero [OK]

Common Mistakes:

• Stopping too early and returning wrong remainder
• Confusing modulo with division
• Mixing up order of parameters

4. The following code attempts to compute the LCM of two numbers using their GCD. Identify the bug:

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

function lcm(a, b) {
  return (a * b) / gcd(a, b);
}

console.log(lcm(4, 6));

medium

A. The gcd function modifies a and b directly, affecting lcm calculation

B. The lcm function should add instead of multiply a and b

C. The gcd function should return b instead of a

D. There is no bug; the code correctly calculates LCM

Solution

1. Step 1: Understand variable mutation in gcd function

   The gcd function changes a and b inside the loop, so after calling gcd, a and b in lcm are modified.

2. Step 2: Impact on lcm calculation

   Since a and b are changed by gcd, the multiplication a * b in lcm uses modified values, causing incorrect LCM.

3. Final Answer:

   The gcd function modifies a and b directly, affecting lcm calculation -> Option A

4. Quick Check:

   Mutating inputs in gcd breaks lcm formula [OK]

Hint: Avoid changing input variables when computing GCD for LCM [OK]

Common Mistakes:

• Assuming gcd doesn't change inputs
• Using addition instead of multiplication in LCM
• Returning wrong variable from gcd

5. Given an array of positive integers [12, 15, 20], which JavaScript function correctly computes the LCM of all elements using the Euclidean algorithm for GCD?

hard

A. function gcd(a, b) { while(b !== 0) { let t = b; b = a % b; a = t; } return a; } function lcm(a, b) { return (a * b) / gcd(a, b); } function lcmArray(arr) { return arr.reduce((acc, val) => lcm(acc, val)); } console.log(lcmArray([12, 15, 20]));

B. function gcd(a, b) { return a + b; } function lcm(a, b) { return a * b; } function lcmArray(arr) { return arr.reduce((acc, val) => lcm(acc, val)); } console.log(lcmArray([12, 15, 20]));

C. function gcd(a, b) { while(a !== 0) { a = b % a; b = a; } return b; } function lcm(a, b) { return (a + b) / gcd(a, b); } function lcmArray(arr) { return arr.reduce((acc, val) => lcm(acc, val)); } console.log(lcmArray([12, 15, 20]));

D. function gcd(a, b) { while(b !== 0) { let t = b; b = a % b; a = t; } return a; } function lcm(a, b) { return (a * b) * gcd(a, b); } function lcmArray(arr) { return arr.reduce((acc, val) => lcm(acc, val)); } console.log(lcmArray([12, 15, 20]));

Solution

1. Step 1: Verify gcd and lcm functions correctness

   function gcd(a, b) { while(b !== 0) { let t = b; b = a % b; a = t; } return a; } function lcm(a, b) { return (a * b) / gcd(a, b); } function lcmArray(arr) { return arr.reduce((acc, val) => lcm(acc, val)); } console.log(lcmArray([12, 15, 20])); uses correct Euclidean gcd and calculates lcm as (a*b)/gcd(a,b), which is mathematically correct.

2. Step 2: Check lcmArray function logic

   It uses reduce to apply lcm pairwise across the array, correctly computing LCM of all elements.

3. Step 3: Validate other options

   function gcd(a, b) { return a + b; } function lcm(a, b) { return a * b; } function lcmArray(arr) { return arr.reduce((acc, val) => lcm(acc, val)); } console.log(lcmArray([12, 15, 20])); uses incorrect gcd and lcm formulas. function gcd(a, b) { while(a !== 0) { a = b % a; b = a; } return b; } function lcm(a, b) { return (a + b) / gcd(a, b); } function lcmArray(arr) { return arr.reduce((acc, val) => lcm(acc, val)); } console.log(lcmArray([12, 15, 20])); has wrong gcd and lcm formulas. function gcd(a, b) { while(b !== 0) { let t = b; b = a % b; a = t; } return a; } function lcm(a, b) { return (a * b) * gcd(a, b); } function lcmArray(arr) { return arr.reduce((acc, val) => lcm(acc, val)); } console.log(lcmArray([12, 15, 20])); incorrectly multiplies gcd in lcm formula.

4. Final Answer:

   Option A code correctly computes LCM of array elements -> Option A

5. Quick Check:

   Correct gcd, lcm, and reduce for array LCM [OK]

Hint: Use reduce with correct gcd and lcm formulas for arrays [OK]

Common Mistakes:

• Incorrect gcd or lcm formulas
• Not using reduce to combine array elements
• Multiplying gcd instead of dividing in lcm