GCD and LCM Euclidean Algorithm in DSA Javascript

Mental Model

GCD is the biggest number that divides two numbers without leftovers. LCM is the smallest number both can fit into evenly. Euclid's method finds GCD by subtracting or dividing until the remainder is zero.

Analogy: Imagine you have two ropes of different lengths. To find the biggest equal piece you can cut from both without leftovers (GCD), you keep cutting the longer rope by the length of the shorter one until they match. For LCM, think of finding the shortest length that both ropes can be stretched to without breaking.

Number A: 48
Number B: 18

GCD process:
48 % 18 = 12
18 % 12 = 6
12 % 6 = 0

So GCD is 6

LCM = (48 * 18) / 6 = 144

Dry Run Walkthrough

Input: Find GCD and LCM of 48 and 18

Goal: Calculate the greatest common divisor (GCD) and least common multiple (LCM) of 48 and 18 using Euclid's algorithm

Step 1: Calculate remainder of 48 divided by 18

48 % 18 = 12

Why: We find remainder to reduce the problem size

Step 2: Calculate remainder of 18 divided by 12

18 % 12 = 6

Why: Continue reducing until remainder is zero

Step 3: Calculate remainder of 12 divided by 6

12 % 6 = 0

Why: Remainder zero means divisor 6 is the GCD

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

LCM = 144

Why: LCM is product divided by GCD

Result:

GCD = 6
LCM = 144

Annotated Code

DSA Javascript

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

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

// Driver code
const num1 = 48;
const num2 = 18;
const gcd = Euclidean.gcd(num1, num2);
const lcm = Euclidean.lcm(num1, num2);
console.log(`GCD = ${gcd}`);
console.log(`LCM = ${lcm}`);

while (b !== 0) {

repeat until remainder is zero

const remainder = a % b; // find remainder

calculate remainder to reduce problem

a = b; // move b to a

shift b to a for next iteration

b = remainder; // remainder becomes new b

update b to remainder for next step

return a; // when b is 0, a is gcd

final gcd found when remainder zero

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

calculate lcm using gcd

Output

GCD = 6

LCM = 144

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: Euclid's 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

GCD is the non-zero number, LCM is zero

DSA Javascript

while (b !== 0) {

Both numbers are equal

GCD is the number itself, LCM is the same number

DSA Javascript

while (b !== 0) {

One number is 1

GCD is 1, LCM is the other number

DSA Javascript

while (b !== 0) {

When to Use This Pattern

When you need to find the greatest common divisor or least common multiple efficiently, reach for Euclid's algorithm because it quickly reduces the problem using remainders.

Common Mistakes

Mistake: Stopping the loop when remainder is not zero instead of when it is zero
Fix: Change loop condition to continue while remainder (b) is not zero

Mistake: Calculating LCM without dividing by GCD
Fix: Use formula LCM = (a * b) / GCD(a, b) to avoid incorrect results

Summary

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

Use when you need fast and reliable calculation of GCD and LCM.

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 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