GCD and LCM Euclidean Algorithm in DSA Typescript - Execution Trace

Concept Flow - GCD and LCM Euclidean Algorithm

Start with two numbers a and b

↓

Check if b == 0?

Yes→GCD is a

No↓

Calculate remainder r = a % b

↓

Set a = b, b = r

↓

Repeat check b == 0?

↓

After GCD found

↓

Calculate LCM = (original_a * original_b) / GCD

↓

Done

Start with two numbers, repeatedly replace a by b and b by remainder until b is zero. The last non-zero a is GCD. Then calculate LCM using GCD.

Execution Sample

DSA Typescript

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

function lcm(a: number, b: number): number {
  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	Remainder (a % b)	Action	GCD Found	LCM Calculation	Visual State
1	Start	48	18	-	Check b != 0	No	-	a=48, b=18
2	Calculate remainder	48	18	12	a=18, b=12	No	-	a=18, b=12
3	Calculate remainder	18	12	6	a=12, b=6	No	-	a=12, b=6
4	Calculate remainder	12	6	0	a=6, b=0	Yes	-	a=6, b=0
5	GCD found	6	0	-	Stop loop	Yes	-	GCD=6
6	Calculate LCM	48	18	-	-	Yes	LCM = (48*18)/6 = 144	LCM=144

💡 Loop stops when b becomes 0 at step 4; GCD is last non-zero a which is 6.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	Final
a	48	48	18	12	6	6
b	18	18	12	6	0	0
r	-	12	6	0	-	-
GCD	-	-	-	-	6	6
LCM	-	-	-	-	-	144

Key Moments - 3 Insights

Why do we stop the loop when b becomes zero?

Because when b is zero, the remainder is zero and the current a is the greatest common divisor (GCD). This is shown in execution_table step 4 where b=0 and GCD=6 is found.

Why do we replace a with b and b with remainder each iteration?

This step reduces the problem size while keeping the GCD the same. The remainder is always smaller, so the loop moves towards termination. See execution_table steps 2-4 where a and b update progressively.

How is LCM calculated after finding GCD?

LCM is calculated by multiplying the original two numbers and dividing by their GCD. This ensures the smallest common multiple. Execution_table step 6 shows LCM = (48*18)/6 = 144.

Visual Quiz - 3 Questions

Look at the execution_table, what is the value of 'b' after step 3?

A 0

B 12

C 6

D 18

💡 Hint

Check the 'b' column in execution_table row for step 3.

At which step does the loop stop because b becomes zero?

A Step 2

B Step 4

C Step 5

D Step 6

💡 Hint

Look for the step where 'b' is zero and the loop ends in execution_table.

If the initial numbers were 30 and 12, how would the GCD at the end change?

A GCD would be 6

B GCD would be 12

C GCD would be 18

D GCD would be 30

💡 Hint

Recall GCD of 30 and 12 is the largest number dividing both; think about Euclidean steps.

Concept Snapshot

GCD and LCM Euclidean Algorithm:
- Start with two numbers a and b.
- Repeat: replace a with b, b with a % b until b is 0.
- When b=0, a is GCD.
- Calculate LCM = (original_a * original_b) / GCD.
- Efficient way to find GCD and LCM without factoring.

Full Transcript

The Euclidean algorithm finds the greatest common divisor (GCD) of two numbers by repeatedly replacing the larger number with the remainder of dividing the larger by the smaller. This continues until the remainder is zero. The last non-zero remainder is the GCD. Then, the least common multiple (LCM) is calculated by multiplying the original two numbers and dividing by the GCD. This method is efficient and avoids prime factorization. The execution table shows step-by-step how variables a and b change, how the remainder is calculated, and when the loop stops. The variable tracker shows the values of a, b, remainder, GCD, and LCM at each step. Key moments clarify why the loop stops at b=0, why variables update as they do, and how LCM is computed. The visual quiz tests understanding of variable values at specific steps and the effect of changing input numbers.

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