GCD and LCM Euclidean Algorithm in DSA Rust

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 repeatedly subtracting or dividing until one number becomes zero.

Analogy: Imagine two ropes of different lengths. To find the biggest equal piece you can cut from both without waste (GCD), you keep cutting the longer rope by the length of the shorter one until one rope is fully cut. For LCM, think of finding the smallest length that both ropes can be stretched to without gaps.

a = 48
b = 18

GCD process:
48 -> 18 -> 12 -> 6 -> 0

LCM formula:
LCM = (a * b) / GCD

Dry Run Walkthrough

Input: Find GCD and LCM of 48 and 18

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

Step 1: Calculate remainder of 48 divided by 18

48 % 18 = 12

Why: We replace the bigger number with the remainder to reduce the problem size

Step 2: Calculate remainder of 18 divided by 12

18 % 12 = 6

Why: Continue reducing numbers by remainder to approach zero

Step 3: Calculate remainder of 12 divided by 6

12 % 6 = 0

Why: When remainder is zero, the divisor is the GCD

Step 4: GCD found as 6, calculate LCM using formula

LCM = (48 * 18) / 6 = 144

Why: LCM is product divided by GCD to find smallest common multiple

Result:

GCD = 6
LCM = 144

Annotated Code

DSA Rust

fn gcd(mut a: u32, mut b: u32) -> u32 {
    while b != 0 {
        let temp = b; // store current b
        b = a % b;    // remainder replaces b
        a = temp;     // a takes old b
    }
    a // a is gcd when b is zero
}

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

fn main() {
    let a = 48;
    let b = 18;
    let result_gcd = gcd(a, b);
    let result_lcm = lcm(a, b);
    println!("GCD = {}", result_gcd);
    println!("LCM = {}", result_lcm);
}

while b != 0 {

repeat until remainder is zero

b = a % b;

replace b with remainder of a divided by b

a = temp;

assign old b to a to continue Euclid's steps

(a / gcd(a, b)) * b

calculate LCM using product divided by GCD, rearranged to avoid overflow

Output

GCD = 6

LCM = 144

Complexity Analysis

Time: O(log(min(a, b))) because each step reduces the problem size significantly by remainder

Space: O(1) because only a few variables are used regardless of input size

vs Alternative: Naive approach tries all divisors up to min(a,b), which is O(min(a,b)) and slower than Euclid's efficient division method

Edge Cases

One number is zero (e.g., a=0, b=18)

GCD is the non-zero number, LCM is zero

DSA Rust

while b != 0 {

Both numbers are equal (e.g., a=12, b=12)

GCD is the number itself, LCM is also the same number

DSA Rust

while b != 0 {

One number divides the other exactly (e.g., a=20, b=5)

GCD is the smaller number, LCM is the larger number

DSA Rust

while b != 0 {

When to Use This Pattern

When you need to find the largest number dividing two numbers or the smallest common multiple, reach for Euclid's algorithm because it efficiently uses division and remainder to solve the problem.

Common Mistakes

Mistake: Using subtraction instead of modulo leads to slower or infinite loops
Fix: Use modulo operator (%) to get remainder directly for faster convergence

Summary

Finds the greatest common divisor and least common multiple of two numbers using repeated remainder calculation.

Use when you need to find shared factors or multiples efficiently between two numbers.

The key insight is that GCD of two numbers equals the GCD of the smaller number and the remainder of the larger divided by the smaller.

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