GCD and LCM Euclidean Algorithm in DSA Java

Mental Model

GCD is the biggest number that divides two numbers without leaving a remainder. LCM is the smallest number that both numbers can divide into evenly.

Analogy: Think of two ropes of different lengths. GCD is the longest length you can cut both ropes into equal pieces without leftover. LCM is the shortest length where you can join pieces of both ropes to make the same length.

Number A: 12
Number B: 18

GCD: ?
LCM: ?

Dry Run Walkthrough

Input: Find GCD and LCM of 12 and 18 using Euclidean Algorithm

Goal: Calculate the greatest common divisor (GCD) and least common multiple (LCM) of 12 and 18

Step 1: Calculate remainder of 18 divided by 12

18 % 12 = 6

Why: We use remainder to reduce the problem size

Step 2: Calculate remainder of 12 divided by 6

12 % 6 = 0

Why: When remainder is zero, divisor is the GCD

Step 3: GCD found as 6, calculate LCM using formula (A * B) / GCD

LCM = (12 * 18) / 6 = 36

Why: LCM is derived from GCD to avoid repeated factorization

Result:

GCD = 6
LCM = 36

Annotated Code

DSA Java

public class GcdLcmEuclidean {
    // Function to find GCD using Euclidean Algorithm
    public static 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; // when b is 0, a is GCD
    }

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

    public static void main(String[] args) {
        int a = 12;
        int b = 18;
        int gcdValue = gcd(a, b);
        int lcmValue = lcm(a, b);
        System.out.println("GCD = " + gcdValue);
        System.out.println("LCM = " + lcmValue);
    }
}

while (b != 0) {

repeat until remainder is zero to find GCD

b = a % b;

calculate remainder to reduce problem size

a = temp;

shift values to continue Euclidean steps

return a;

return GCD when remainder is zero

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

calculate LCM using GCD to avoid repeated factorization

Output

GCD = 6

LCM = 36

Complexity Analysis

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

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

vs Alternative: Euclidean 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, 5)

GCD is the non-zero number, LCM is zero

DSA Java

while (b != 0) {

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

GCD is the number itself, LCM is the same number

DSA Java

while (b != 0) {

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

GCD is 1, LCM is the other number

DSA Java

while (b != 0) {

When to Use This Pattern

When you need to find the greatest common divisor or least common multiple efficiently, use the Euclidean algorithm because it quickly reduces the problem using remainders.

Common Mistakes

Mistake: Using subtraction instead of modulo in Euclidean algorithm, which is slower
Fix: Use modulo operator (%) to find remainder for faster convergence

Mistake: Calculating LCM as (a * b) without dividing by GCD, causing 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 the Euclidean algorithm.

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

The key insight is that GCD can be found by repeatedly replacing the larger number with the remainder until zero is reached.

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