GCD and LCM Euclidean Algorithm in DSA C

Mental Model

GCD is the biggest number that divides two numbers without leftover. LCM is the smallest number both can fit into evenly. Euclid's method finds GCD by subtracting or dividing until one number becomes zero.

Analogy: Imagine two ropes of different lengths. To find the longest piece you can cut both ropes into equal pieces without leftover, you keep cutting the longer rope by the length of the shorter one until one rope is fully cut.

Number A: 48
Number B: 18

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

LCM uses GCD:
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 48 with 18 and 18 with remainder 12 to reduce the problem

Step 2: Calculate remainder of 18 divided by 12

18 % 12 = 6

Why: Continue reducing by replacing 18 with 12 and 12 with remainder 6

Step 3: Calculate remainder of 12 divided by 6

12 % 6 = 0

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

Step 4: Calculate LCM using formula (48 * 18) / 6

LCM = 864 / 6 = 144

Why: LCM is found by dividing product by GCD

Result:

GCD = 6
LCM = 144

Annotated Code

DSA C

#include <stdio.h>

// Function to find GCD using Euclidean algorithm
int gcd(int a, int b) {
    while (b != 0) {
        int temp = b;           // store current b
        b = a % b;              // remainder replaces b
        a = temp;               // old b becomes new a
    }
    return a;                   // a is GCD when b is zero
}

// Function to find LCM using GCD
int lcm(int a, int b) {
    return (a / gcd(a, b)) * b; // avoid overflow by dividing first
}

int main() {
    int a = 48, b = 18;
    int result_gcd = gcd(a, b);
    int result_lcm = lcm(a, b);
    printf("GCD = %d\n", result_gcd);
    printf("LCM = %d\n", result_lcm);
    return 0;
}

while (b != 0) {

repeat until remainder is zero

int temp = b;

store current divisor

b = a % b;

replace b with remainder of a divided by b

a = temp;

replace a with old b to continue process

return a;

return GCD when remainder is zero

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

calculate LCM using GCD 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 operation

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

vs Alternative: Euclid's algorithm is much faster than checking all divisors up to min(a,b), which is O(min(a,b))

Edge Cases

One number is zero (e.g., gcd(0, 18))

GCD is the non-zero number, LCM is zero

DSA C

while (b != 0) {

Both numbers are equal (e.g., gcd(12, 12))

GCD is the number itself, LCM is the same number

DSA C

while (b != 0) {

One number is 1 (e.g., gcd(1, 18))

GCD is 1, LCM is the other number

DSA C

while (b != 0) {

When to Use This Pattern

When you need to find the greatest common divisor or least common multiple efficiently, reach for Euclid's algorithm because it quickly reduces the problem using remainders.

Common Mistakes

Mistake: Using subtraction instead of modulo can be slower and more complex
Fix: Use the modulo operator (%) to find remainder for faster convergence

Mistake: Calculating LCM as (a * b) without dividing by GCD can cause overflow
Fix: Calculate LCM as (a / gcd(a, b)) * b to reduce risk of overflow

Summary

Finds the greatest common divisor and least common multiple of two numbers using Euclid's remainder method.

Use when you need fast and reliable calculation of GCD and LCM for two integers.

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