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

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

This code finds the GCD of two numbers using the Euclidean algorithm by repeatedly replacing the larger number with the remainder.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The while loop runs repeatedly, performing a modulo operation each time.
• How many times: The loop runs until the remainder becomes zero, which depends on the size of the inputs.

How Execution Grows With Input

Each step reduces the size of the numbers significantly, so the number of steps grows slowly compared to input size.

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

Pattern observation: The number of steps grows 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 slowly, roughly with the number of digits of the smaller input.

Common Mistake

[X] Wrong: "The algorithm takes time proportional to the input numbers themselves."

[OK] Correct: The Euclidean algorithm reduces numbers quickly, so it does not check every number up to the inputs.

Interview Connect

Understanding this algorithm's time complexity shows you can analyze efficient number-based algorithms, a useful skill in many coding problems.

Self-Check

"What if we used recursion instead of a loop? How would the time complexity change?"

Practice

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

easy

A. The sum of the numbers

B. The Least Common Multiple (LCM)

C. The Greatest Common Divisor (GCD)

D. The difference between the numbers

Solution

1. Step 1: Understand the 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 and others

   While LCM is related to GCD, the Euclidean algorithm directly computes GCD, not LCM or sums/differences.

3. Final Answer:

   The Greatest Common Divisor (GCD) -> Option C

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 finds prime factors directly

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

easy

A. public static int gcd(int a, int b)

B. public int gcd(int a, int b, int c)

C. static void gcd(int a, int b)

D. public static int gcd()

Solution

1. Step 1: Check method parameters and return type

   The method should take two integers as input and return an integer representing the GCD.

2. Step 2: Validate method signature correctness

   public static int gcd(int a, int b) matches this: it is static, returns int, and takes two int parameters. Others have wrong parameters or return type.

3. Final Answer:

   public static int gcd(int a, int b) -> Option A

4. Quick Check:

   Correct signature = public static int gcd(int a, int b) [OK]

Hint: GCD method needs two int inputs and int return [OK]

Common Mistakes:

• Adding extra parameters unnecessarily
• Using void return type instead of int
• Omitting static keyword when needed

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

public class Test {
  public static int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
  }
  public static void main(String[] args) {
    System.out.println(gcd(48, 18));
  }
}

medium

A. 6

B. 12

C. 18

D. 3

Solution

1. Step 1: Trace gcd(48, 18) calls

   gcd(48,18) calls gcd(18, 48%18=12), then gcd(18,12) calls gcd(12, 18%12=6), then gcd(12,6) calls gcd(6, 12%6=0), returns 6.

2. Step 2: Final return value

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

3. Final Answer:

   6 -> Option A

4. Quick Check:

   GCD(48,18) = 6 [OK]

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

Common Mistakes:

• Stopping too early without full recursion
• Mixing up modulo operation
• Returning wrong variable when b=0

4. Identify the error in the following Java method for computing LCM using GCD and fix it:

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

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

medium

A. Return b instead of a in gcd method

B. gcd method should be static void

C. No error; code is correct

D. Use Math.abs(a * b) to avoid negative LCM

Solution

1. Step 1: Analyze LCM calculation

   LCM is calculated as (a * b) / GCD(a, b). If a or b is negative, product can be negative, causing wrong LCM.

2. Step 2: Fix negative product issue

   Use Math.abs(a * b) to ensure LCM is always positive.

3. Final Answer:

   Use Math.abs(a * b) to avoid negative LCM -> Option D

4. Quick Check:

   LCM must be positive; abs fixes sign [OK]

Hint: Use absolute value for product in LCM formula [OK]

Common Mistakes:

• Ignoring negative inputs causing wrong LCM
• Changing gcd return type incorrectly
• Returning wrong variable in gcd method

5. Given an array of integers nums = {12, 15, 20}, which Java code snippet correctly computes the LCM of all elements using the Euclidean algorithm?

hard

A. int lcm = 1; for(int i=0; i

B. int lcm = nums[0]; for(int i=1; i

C. int lcm = nums[0]; for(int i=1; i

D. int lcm = 0; for(int i=0; i

Solution

1. Step 1: Understand LCM of multiple numbers

   LCM of multiple numbers can be found by iteratively computing LCM of pairs: lcm(a,b,c) = lcm(lcm(a,b), c).

2. Step 2: Check code correctness

   int lcm = nums[0]; for(int i=1; i

3. Final Answer:

   int lcm = nums[0]; for(int i=1; i -> Option B

4. Quick Check:

   Iterative LCM with gcd formula works [OK]

Hint: Iterate LCM pairwise using lcm = (a*b)/gcd(a,b) [OK]

Common Mistakes:

• Using gcd instead of lcm in loop
• Summing elements instead of computing LCM
• Starting lcm from 0 causing division errors