GCD and LCM Euclidean Algorithm in DSA Javascript - Execution Trace

Concept Flow - GCD and LCM Euclidean Algorithm

Start with two numbers a, b

↓

Check if b == 0?

Yes→GCD is a

No↓

Calculate a % b

↓

Set a = b, b = a % b

↓

Repeat until b == 0

↓

Calculate LCM = (original_a * original_b) / GCD

Start with two numbers, repeatedly replace the larger by remainder until zero; last non-zero is GCD. Then use GCD to find LCM.

Execution Sample

DSA Javascript

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);
}

This code finds the GCD of two numbers using the Euclidean algorithm and then calculates the LCM using the GCD.

Execution Table

Step	Operation	a	b	a % b	Pointer Changes	Visual State
1	Start with a=48, b=18	48	18	N/A	Initial values set	a=48, b=18
2	Check b != 0	48	18	N/A	b=18 not zero, continue	a=48, b=18
3	Calculate a % b	48	18	12	temp=b=18; b=a%b=12; a=temp=18	a=18, b=12
4	Check b != 0	18	12	N/A	b=12 not zero, continue	a=18, b=12
5	Calculate a % b	18	12	6	temp=b=12; b=a%b=6; a=temp=12	a=12, b=6
6	Check b != 0	12	6	N/A	b=6 not zero, continue	a=12, b=6
7	Calculate a % b	12	6	0	temp=b=6; b=a%b=0; a=temp=6	a=6, b=0
8	Check b != 0	6	0	N/A	b=0, stop loop	a=6, b=0
9	Return GCD	6	0	N/A	GCD is a=6	GCD=6
10	Calculate LCM	48	18	N/A	LCM = (48*18)/6 = 144	LCM=144

💡 Loop stops when b becomes 0; last a is GCD; LCM calculated using GCD.

Variable Tracker

Variable	Start	After 1	After 2	After 3	After 4	After 5	Final
a	48	18	12	6	6	6	6
b	18	12	6	0	0	0	0
temp	N/A	18	12	6	6	6	N/A

Key Moments - 3 Insights

Why do we swap a and b using temp during each iteration?

We store b in temp before changing b to a % b, so we can assign a = temp. This keeps the previous b as the new a for the next step, as shown in steps 3, 5, and 7 in the execution_table.

Why does the loop stop when b becomes zero?

The Euclidean algorithm states that when b is zero, the current a is the GCD. This is shown in step 8 where b=0 stops the loop and step 9 returns a as GCD.

How is LCM calculated from GCD?

LCM is calculated by multiplying the original two numbers and dividing by their GCD, as shown in step 10 of the execution_table.

Visual Quiz - 3 Questions

Look at the execution_table at step 5, what is the value of b after the operation?

A 0

B 12

C 6

D 18

💡 Hint

Check the 'b' column in execution_table row 5.

At which step does the condition b !== 0 become false?

A Step 7

B Step 8

C Step 9

D Step 10

💡 Hint

Look at the 'Check b != 0' operations and see when b is zero.

If we change the initial numbers to a=30 and b=12, how would the final GCD change?

A It would be 6

B It would be 12

C It would be 18

D It would be 30

💡 Hint

Recall GCD of 30 and 12 is the largest number dividing both; check variable_tracker logic.

Concept Snapshot

Euclidean Algorithm for GCD:
- Repeat: a, b = b, a % b until b == 0
- GCD is last non-zero a
- LCM = (original_a * original_b) / GCD
- Uses remainder to reduce problem size
- Efficient and fast for large numbers

Full Transcript

This visual trace shows how the Euclidean algorithm finds the greatest common divisor (GCD) of two numbers by repeatedly replacing the larger number with the remainder of dividing the two numbers until the remainder is zero. The last non-zero number is the GCD. Then, the least common multiple (LCM) is calculated by multiplying the original two numbers and dividing by the GCD. The execution table tracks each step, showing how variables a and b change, how the remainder is calculated, and when the loop stops. Key moments clarify why swapping variables is necessary, why the loop stops at zero, and how LCM is derived from GCD. The quiz tests understanding of variable values at specific steps and the stopping condition.

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