GCD and LCM Euclidean Algorithm in DSA Javascript - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to return the greatest common divisor (GCD) of two numbers using the Euclidean algorithm.

DSA Javascript

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

Drag options to blanks, or click blank then click option'

Atemp

Ba

Cb

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Using a % a instead of a % b

Swapping variables incorrectly

Returning b instead of a

The Euclidean algorithm replaces a by b and b by a % b until b becomes zero. So, a % b is the correct expression.

2fill in blank

medium

Complete the code to calculate the least common multiple (LCM) of two numbers using their GCD.

DSA Javascript

function lcm(a, b) {
  return (a * b) / [1](a, b);
}

Drag options to blanks, or click blank then click option'

Amin

Bgcd

Cmax

Dabs

Attempts:

3 left

💡 Hint

Common Mistakes

Using max or min instead of gcd

Forgetting to divide by gcd

Multiplying by gcd instead of dividing

The formula for LCM is (a * b) / gcd(a, b). So, we use the gcd function here.

3fill in blank

hard

Fix the error in the recursive GCD function by completing the base case condition.

DSA Javascript

function gcdRecursive(a, b) {
  if (b [1] 0) {
    return a;
  }
  return gcdRecursive(b, a % b);
}

Drag options to blanks, or click blank then click option'

A==

B!=

C>

D<

Attempts:

3 left

💡 Hint

Common Mistakes

Using != instead of ==

Using > or < which causes wrong base case

Missing the base case entirely

The base case for the recursive GCD is when b == 0. Then, a is the GCD.

4fill in blank

hard

Fill both blanks to create a function that returns an object with GCD and LCM of two numbers.

DSA Javascript

function gcdAndLcm(a, b) {
  const gcdValue = [1](a, b);
  const lcmValue = (a * b) / [2];
  return { gcd: gcdValue, lcm: lcmValue };
}

Drag options to blanks, or click blank then click option'

Agcd

Blcm

CgcdValue

DlcmValue

Attempts:

3 left

💡 Hint

Common Mistakes

Using lcm function inside itself causing recursion

Dividing by lcmValue which is not defined yet

Mixing variable names

First, we call the gcd function to get the GCD. Then, we divide the product by gcdValue to get the LCM.

5fill in blank

hard

Fill all three blanks to create a function that returns an array with GCD and LCM of two numbers using recursion.

DSA Javascript

function gcdLcmArray(a, b) {
  const gcdValue = [1](a, b);
  const lcmValue = (a * b) / [2];
  return [gcdValue, [3]];
}

Drag options to blanks, or click blank then click option'

AgcdRecursive

BgcdValue

ClcmValue

DlcmRecursive

Attempts:

3 left

💡 Hint

Common Mistakes

Using undefined lcmRecursive function

Returning variables in wrong order

Forgetting to use gcdValue in LCM calculation

We use the recursive gcd function gcdRecursive to get gcdValue. Then calculate lcmValue. Finally, return an array with gcdValue and lcmValue.

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