GCD and LCM Euclidean Algorithm in DSA C - 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

↓

Done

Start with two numbers, repeatedly replace a by b and b by a mod b until b is zero. The last non-zero a is the GCD. Then compute LCM using the formula.

Execution Sample

DSA C

int gcd(int a, int b) {
  while (b != 0) {
    int temp = b;
    b = a % b;
    a = temp;
  }
  return a;
}

int lcm(int a, int b) {
  return (a / gcd(a, b)) * 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	a=48, b=18	a=48, b=18
2	Calculate a % b	48	18	12	temp=b=18; b=48%18=12; a=temp=18	a=18, b=12
3	Calculate a % b	18	12	6	temp=b=12; b=18%12=6; a=temp=12	a=12, b=6
4	Calculate a % b	12	6	0	temp=b=6; b=12%6=0; a=temp=6	a=6, b=0
5	b == 0, GCD found	6	0	N/A	Stop loop	GCD=6
6	Calculate LCM	48	18	N/A	LCM = (48 / 6) * 18 = 8 * 18 = 144	LCM=144

💡 Loop stops 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	Final
a	48	18	12	6	6	6
b	18	12	6	0	0	0
temp	N/A	18	12	6	N/A	N/A
GCD	N/A	N/A	N/A	N/A	6	6
LCM	N/A	N/A	N/A	N/A	N/A	144

Key Moments - 3 Insights

Why do we replace a with b and b with a % b in each step?

Because the Euclidean algorithm uses the property that GCD(a, b) = GCD(b, a % b). This reduces the problem size each step until b becomes zero, as shown in steps 2-4 in the execution_table.

Why does the loop stop when b becomes zero?

When b is zero, the current value of a is the GCD. This is because no number divides zero except the number itself. This is shown in step 5 where b=0 and GCD=6.

How is LCM calculated using GCD?

LCM is calculated by dividing the product of the original numbers by their GCD: LCM = (a * b) / GCD. This is shown in step 6 where LCM = (48 / 6) * 18 = 144.

Visual Quiz - 3 Questions

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

A 6

B 18

C 12

D 48

💡 Hint

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

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

A Step 5

B Step 4

C Step 6

D Step 3

💡 Hint

Look for the step where b becomes 0 in the execution_table.

If the initial numbers were 30 and 12, how would the final GCD value in variable_tracker change?

A It would be 18

B It would be 6

C It would be 12

D It would be 30

💡 Hint

Recall that GCD(30,12) is 6, similar to the example's GCD calculation.

Concept Snapshot

GCD (Greatest Common Divisor) finds the largest number dividing two numbers.
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 large numbers.

Full Transcript

We start with two numbers a and b. We check if b is zero. If not, we calculate a modulo b and update a and b accordingly. We repeat this until b becomes zero. The last non-zero a is the GCD. Then we calculate the LCM by dividing the product of the original numbers by the GCD. This method is called the Euclidean algorithm and is efficient for finding GCD and LCM.

Practice

1. What does the Euclidean algorithm primarily calculate between two numbers a and b?

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

2. Which of the following is the correct syntax for the Euclidean algorithm function header in C to find GCD of two integers a and b?

easy

A. int gcd(int a, int b);

B. void gcd(int a, int b);

C. float gcd(int a, int b);

D. int gcd(float a, float b);

Solution

1. Step 1: Identify return type for GCD function

   GCD is an integer value, so the function should return int.

2. Step 2: Check parameter types

   Parameters a and b should be integers for GCD calculation.

3. Final Answer:

   int gcd(int a, int b); -> Option A

4. Quick Check:

   Function returns int and takes int parameters [OK]

Hint: GCD function returns int and takes int parameters [OK]

Common Mistakes:

• Using void return type for GCD
• Using float parameters or return type
• Missing parameter types

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

int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

int main() {
    printf("%d", gcd(48, 18));
    return 0;
}

medium

A. 12

B. 6

C. 18

D. 3

Solution

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

   Calculate gcd(48,18): 48 % 18 = 12, so gcd(18,12). Then 18 % 12 = 6, gcd(12,6). Then 12 % 6 = 0, gcd(6,0) = 6.

2. Step 2: Return the last non-zero remainder

   When second parameter is 0, return first parameter which is 6.

3. Final Answer:

   6 -> Option B

4. Quick Check:

   GCD(48,18) = 6 [OK]

Hint: Use remainder until zero to find GCD [OK]

Common Mistakes:

• Returning wrong remainder
• Confusing order of parameters
• Stopping before remainder is zero

4. Identify the error in the following C function to compute LCM using GCD:

int gcd(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

int lcm(int a, int b) {
    return a * b / gcd(a, b);
}

medium

A. No error, code is correct

B. GCD function has infinite loop

C. LCM function should use addition instead of multiplication

D. LCM function may cause integer overflow

Solution

1. Step 1: Analyze GCD function correctness

   The GCD function uses Euclidean algorithm correctly with a loop and swapping variables.

2. Step 2: Check LCM calculation for potential issues

   LCM is calculated as (a * b) / gcd(a, b). Multiplying a and b first can cause integer overflow if numbers are large.

3. Final Answer:

   LCM function may cause integer overflow -> Option D

4. Quick Check:

   Multiplying before dividing risks overflow [OK]

Hint: Multiply after dividing by GCD to avoid overflow [OK]

Common Mistakes:

• Assuming no overflow risk
• Thinking GCD function loops infinitely
• Using addition instead of multiplication in LCM

5. Given an array of positive integers arr = {12, 15, 20}, which of the following C code snippets correctly computes the LCM of all elements using the Euclidean algorithm?

hard

A. int gcd(int a, int b) {
if (b == 0) return a;
return gcd(b, a % b);
}

int lcm(int a, int b) {
return (a / gcd(a, b)) * b;
}

int main() {
int arr[] = {12, 15, 20};
int result = arr[0];
for (int i = 1; i < 3; i++) {
result = lcm(result, arr[i]);
}
printf("%d", result);
return 0;
}

B. int gcd(int a, int b) {
while (b != 0) {
int temp = b;
b = a % b;
a = temp;
}
return a;
}

int lcm(int a, int b) {
return a * b / gcd(a, b);
}

int main() {
int arr[] = {12, 15, 20};
int result = 1;
for (int i = 0; i < 3; i++) {
result = lcm(result, arr[i]);
}
printf("%d", result);
return 0;
}

C. int gcd(int a, int b) {
if (b == 0) return a;
return gcd(b, a % b);
}

int lcm(int a, int b) {
return a + b - gcd(a, b);
}

int main() {
int arr[] = {12, 15, 20};
int result = arr[0];
for (int i = 1; i < 3; i++) {
result = lcm(result, arr[i]);
}
printf("%d", result);
return 0;
}

D. int gcd(int a, int b) {
if (b == 0) return a;
return gcd(b, a % b);
}

int lcm(int a, int b) {
return (a * b) / gcd(a, b);
}

int main() {
int arr[] = {12, 15, 20};
int result = arr[0];
for (int i = 1; i < 3; i++) {
result = lcm(result, arr[i]);
}
printf("%d", result);
return 0;
}

Solution

1. Step 1: Understand LCM calculation in options

   int gcd(int a, int b) {
       if (b == 0) return a;
       return gcd(b, a % b);
   }
   
   int lcm(int a, int b) {
       return (a / gcd(a, b)) * b;
   }
   
   int main() {
       int arr[] = {12, 15, 20};
       int result = arr[0];
       for (int i = 1; i < 3; i++) {
           result = lcm(result, arr[i]);
       }
       printf("%d", result);
       return 0;
   }

   uses lcm(a,b) = (a / gcd(a,b)) * b which avoids overflow and is correct.

   int gcd(int a, int b) {
       while (b != 0) {
           int temp = b;
           b = a % b;
           a = temp;
       }
       return a;
   }
   
   int lcm(int a, int b) {
       return a * b / gcd(a, b);
   }
   
   int main() {
       int arr[] = {12, 15, 20};
       int result = 1;
       for (int i = 0; i < 3; i++) {
           result = lcm(result, arr[i]);
       }
       printf("%d", result);
       return 0;
   }

   starts with result=1 which is valid but risks overflow.

   int gcd(int a, int b) {
       if (b == 0) return a;
       return gcd(b, a % b);
   }
   
   int lcm(int a, int b) {
       return a + b - gcd(a, b);
   }
   
   int main() {
       int arr[] = {12, 15, 20};
       int result = arr[0];
       for (int i = 1; i < 3; i++) {
           result = lcm(result, arr[i]);
       }
       printf("%d", result);
       return 0;
   }

   uses incorrect formula (addition).

   int gcd(int a, int b) {
       if (b == 0) return a;
       return gcd(b, a % b);
   }
   
   int lcm(int a, int b) {
       return (a * b) / gcd(a, b);
   }
   
   int main() {
       int arr[] = {12, 15, 20};
       int result = arr[0];
       for (int i = 1; i < 3; i++) {
           result = lcm(result, arr[i]);
       }
       printf("%d", result);
       return 0;
   }

   uses multiplication first risking overflow.

2. Step 2: Check iteration and initialization

   int gcd(int a, int b) {
       if (b == 0) return a;
       return gcd(b, a % b);
   }
   
   int lcm(int a, int b) {
       return (a / gcd(a, b)) * b;
   }
   
   int main() {
       int arr[] = {12, 15, 20};
       int result = arr[0];
       for (int i = 1; i < 3; i++) {
           result = lcm(result, arr[i]);
       }
       printf("%d", result);
       return 0;
   }

   initializes result with first element and iterates from second element, correctly accumulating LCM. This is the safest and correct approach.

3. Final Answer:

   Option A code snippet correctly computes LCM of all elements -> Option A

4. Quick Check:

   LCM = (a / GCD) * b and accumulate [OK]

Hint: Use (a / gcd) * b to avoid overflow when computing LCM [OK]

Common Mistakes:

• Using addition instead of multiplication for LCM
• Starting with result=1 causing overflow
• Multiplying before dividing causing overflow