GCD and LCM Euclidean Algorithm in DSA C - Time & Space Complexity

Time Complexity: GCD and LCM Euclidean Algorithm

O(log min(a, b))

Understanding Time Complexity

We want to understand how fast the Euclidean algorithm finds the greatest common divisor (GCD) of two numbers.

How does the number of steps grow as the input numbers get bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The while loop repeatedly calculates the remainder of division (a % b).
• How many times: The loop runs until the remainder becomes zero, which depends on the size of the inputs.

How Execution Grows With Input

The number of steps grows slowly compared to the size of the numbers. Each step reduces the problem size significantly.

Input Size (n)	Approx. Operations
10	Up to 5 steps
100	Up to 7 steps
1000	Up to 10 steps

Pattern observation: The steps increase slowly, roughly proportional to the number of digits, not the number itself.

Final Time Complexity

Time Complexity: O(log min(a, b))

This means the steps grow roughly with the number of digits of the smaller input, making it very efficient.

Common Mistake

[X] Wrong: "The algorithm takes time proportional to the input numbers themselves (like O(n))."

[OK] Correct: Each step reduces the numbers quickly by using remainders, so the number of steps grows much slower than the input size.

Interview Connect

Knowing the Euclidean algorithm's time complexity shows you understand efficient number operations, a useful skill in many coding problems.

Self-Check

"What if we used subtraction instead of modulo in the GCD calculation? How would the time complexity change?"

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