GCD and LCM Euclidean Algorithm in DSA Rust - Execution Trace

Concept Flow - GCD and LCM Euclidean Algorithm

Start with two numbers a, b

↓

Check if b == 0?

Yes→GCD is a

No↓

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

fn gcd(mut a: u32, mut b: u32) -> u32 {
    while b != 0 {
        let temp = b;
        b = a % b;
        a = temp;
    }
    a
}

fn lcm(a: u32, b: u32) -> u32 {
    (a * b) / gcd(a, b)
}

Calculates GCD using Euclidean algorithm and then LCM using GCD.

Execution Table

Step	Operation	a	b	a % b	GCD Found?	Visual State
1	Start with a=48, b=18	48	18	N/A	No	a=48, b=18
2	Compute a % b = 48 % 18	48	18	12	No	a=48, b=18, remainder=12
3	Set a = b, b = a % b	18	12	N/A	No	a=18, b=12
4	Compute a % b = 18 % 12	18	12	6	No	a=18, b=12, remainder=6
5	Set a = b, b = a % b	12	6	N/A	No	a=12, b=6
6	Compute a % b = 12 % 6	12	6	0	No	a=12, b=6, remainder=0
7	Set a = b, b = a % b	6	0	N/A	Yes	a=6, b=0; GCD=6
8	Calculate LCM = (48 * 18) / 6	48	18	N/A	Yes	LCM=144

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

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	Final
a	48	48	18	18	12	12	6	6
b	18	18	12	12	6	6	0	0
a % b	N/A	12	N/A	6	N/A	0	N/A	N/A
GCD	N/A	N/A	N/A	N/A	N/A	N/A	6	6
LCM	N/A	N/A	N/A	N/A	N/A	N/A	N/A	144

Key Moments - 3 Insights

Why do we stop when b becomes zero?

Because when b is zero, the last non-zero a is the greatest common divisor (GCD). This is shown in step 7 of the execution_table where b=0 and GCD=6.

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

This follows the Euclidean algorithm logic: the GCD of (a, b) is the same as GCD(b, a % b). This is shown in steps 3, 5, and 7 where a and b are updated accordingly.

How is LCM calculated from GCD?

LCM is calculated using the formula (a * b) / GCD. This is shown in step 8 where LCM=144 is computed from original numbers 48 and 18 and GCD=6.

Visual Quiz - 3 Questions

Look at the execution_table, what is the value of 'a' after step 5?

A 6

B 18

C 12

D 48

💡 Hint

Check the 'a' column in execution_table row for step 5.

At which step does the condition 'b == 0' become true?

A Step 7

B Step 6

C Step 8

D Step 5

💡 Hint

Look at the 'b' column and 'GCD Found?' column in execution_table.

If the initial numbers were 30 and 12, how would the final GCD compare to the one in the table?

A It would be smaller than 6

B It would be equal to 6

C It would be larger than 6

D It would be zero

💡 Hint

Recall that GCD divides both numbers; 6 divides both 30 and 12.

Concept Snapshot

GCD (Greatest Common Divisor) finds largest number dividing both inputs.
Use Euclidean algorithm: repeatedly replace (a, b) with (b, a % b) until b=0.
Last non-zero a is GCD.
LCM (Least Common Multiple) = (a * b) / GCD.
Efficient and fast for positive integers.

Full Transcript

This visual trace shows how the Euclidean algorithm calculates the GCD of two numbers by repeatedly replacing the pair (a, b) with (b, a % b) until b becomes zero. The last non-zero value of a is the GCD. Then, the LCM is calculated using the formula (a * b) / GCD. The execution table tracks each step, showing the values of a, b, and the remainder. Key moments clarify why the loop stops when b is zero, why the values are updated as they are, and how LCM is derived from GCD. The quiz tests understanding of variable values at specific steps and the relationship between GCD and LCM.

Practice

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

easy

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

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

C. The sum of a and b

D. The difference between a and b

Solution

1. Step 1: Understand Euclidean algorithm purpose

   The Euclidean algorithm is designed to find the greatest common divisor (GCD) of two integers by repeatedly applying the remainder operation.

2. Step 2: Differentiate GCD from LCM

   While GCD is the largest number dividing both without remainder, LCM is the smallest number divisible by both. Euclidean algorithm directly finds GCD.

3. Final Answer:

   The greatest common divisor (GCD) of a and b -> Option A

4. Quick Check:

   Euclidean algorithm = GCD [OK]

Hint: Euclidean algorithm finds GCD, not LCM or sums [OK]

Common Mistakes:

• Confusing GCD with LCM
• Thinking it calculates sum or difference
• Assuming it returns both GCD and LCM

2. Which of the following Rust function signatures correctly represents a function to compute the GCD of two unsigned integers using the Euclidean algorithm?

easy

A. fn gcd(a: u32, b: u32) -> u32

B. fn gcd(a: i32, b: i32) -> i32

C. fn gcd(a: u32, b: u32) -> bool

D. fn gcd(a: u32, b: u32)

Solution

1. Step 1: Identify correct parameter and return types

   GCD function takes two unsigned integers (u32) and returns an unsigned integer (u32) representing the GCD.

2. Step 2: Check function signature correctness

   fn gcd(a: u32, b: u32) -> u32 matches this: inputs are u32, output is u32. fn gcd(a: i32, b: i32) -> i32 uses signed integers, which is less common for GCD. fn gcd(a: u32, b: u32) -> bool returns bool, incorrect. fn gcd(a: u32, b: u32) lacks return type.

3. Final Answer:

   fn gcd(a: u32, b: u32) -> u32 -> Option A

4. Quick Check:

   Correct signature returns u32 [OK]

Hint: GCD inputs and output are unsigned integers [OK]

Common Mistakes:

• Using signed integers instead of unsigned
• Missing return type in function signature
• Returning wrong type like bool

3. What is the output of the following Rust code snippet?

fn gcd(mut a: u32, mut b: u32) -> u32 {
    while b != 0 {
        let temp = b;
        b = a % b;
        a = temp;
    }
    a
}

fn main() {
    let result = gcd(48, 18);
    println!("{}", result);
}

medium

A. 12

B. 6

C. 18

D. 3

Solution

1. Step 1: Trace Euclidean algorithm steps for gcd(48, 18)

   Start with a=48, b=18. Compute remainder: 48 % 18 = 12. Update a=18, b=12. Next, 18 % 12 = 6. Update a=12, b=6. Then, 12 % 6 = 0. Update a=6, b=0.

2. Step 2: Identify when loop ends and return value

   Loop ends when b=0. Return a=6 as GCD.

3. Final Answer:

   6 -> Option B

4. Quick Check:

   GCD(48,18) = 6 [OK]

Hint: Use remainder steps until second number is zero [OK]

Common Mistakes:

• Returning the last remainder instead of last non-zero divisor
• Mixing up a and b updates
• Stopping loop too early

4. The following Rust function is intended to compute the LCM of two numbers using their GCD. Identify the error.

fn gcd(mut a: u32, mut b: u32) -> u32 {
    while b != 0 {
        let temp = b;
        b = a % b;
        a = temp;
    }
    a
}

fn lcm(a: u32, b: u32) -> u32 {
    a * b / gcd(a, b)
}

fn main() {
    println!("{}", lcm(0, 0));
}

medium

A. Wrong function signature for LCM

B. Incorrect GCD calculation logic

C. Missing return statement in LCM function

D. Division by zero error when both inputs are zero

Solution

1. Step 1: Analyze the LCM call with zero inputs

   The LCM function computes (a * b) / gcd(a, b). The main calls lcm(0, 0), where gcd(0, 0) returns 0, leading to division by zero.

2. Step 2: Verify gcd(0, 0) behavior

   In gcd, when a=0, b=0, the while loop doesn't execute (b == 0), so it returns a = 0.

3. Final Answer:

   Division by zero error when both inputs are zero -> Option D

4. Quick Check:

   LCM divides by gcd; gcd(0,0)=0 causes error [OK]

Hint: Check zero inputs cause gcd=0 leading to division error [OK]

Common Mistakes:

• Ignoring zero inputs causing division by zero
• Assuming gcd never returns zero
• Not validating inputs before LCM calculation

5. Given a list of positive integers [12, 15, 20], which Rust code snippet correctly computes their LCM using the Euclidean algorithm for GCD?

hard

A. let lcm = nums.iter().fold(1, |acc, &x| gcd(acc, x));

B. let lcm = nums.iter().fold(0, |acc, &x| acc + x / gcd(acc, x));

C. let lcm = nums.iter().fold(1u32, |acc, &x| acc * x / gcd(acc, x));

D. let lcm = nums.iter().fold(1, |acc, &x| acc * x * gcd(acc, x));

Solution

1. Step 1: Understand LCM folding logic

   LCM of multiple numbers can be found by folding with formula: lcm(a,b) = a * b / gcd(a,b). Starting with 1u32, fold applies this stepwise.

2. Step 2: Analyze each option

   let lcm = nums.iter().fold(1u32, |acc, &x| acc * x / gcd(acc, x)); correctly folds with acc * x / gcd(acc, x). let lcm = nums.iter().fold(0, |acc, &x| acc + x / gcd(acc, x)); uses addition, incorrect. let lcm = nums.iter().fold(1, |acc, &x| gcd(acc, x)); returns gcd only, not LCM. let lcm = nums.iter().fold(1, |acc, &x| acc * x * gcd(acc, x)); multiplies by gcd, incorrect.

3. Final Answer:

   let lcm = nums.iter().fold(1u32, |acc, &x| acc * x / gcd(acc, x)); -> Option C

4. Quick Check:

   Fold with acc * x / gcd(acc, x) computes LCM [OK]

Hint: Fold with acc * x / gcd(acc, x) to get LCM of list [OK]

Common Mistakes:

• Using addition instead of multiplication
• Returning gcd instead of LCM
• Multiplying by gcd instead of dividing