GCD and LCM Euclidean Algorithm in DSA Java - Build from Scratch

GCD and LCM using Euclidean Algorithm

📖 Scenario: Imagine you are helping a friend who wants to find the greatest common divisor (GCD) and least common multiple (LCM) of two numbers. These are useful in many real-life situations like sharing items evenly or scheduling events.

🎯 Goal: You will write a Java program that calculates the GCD and LCM of two given numbers using the Euclidean algorithm.

📋 What You'll Learn

Create two integer variables named num1 and num2 with exact values 48 and 18

Create an integer variable named originalNum1 to store the value of num1

Write a while loop that uses the Euclidean algorithm to find the GCD of num1 and num2

Calculate the LCM using the formula: (originalNum1 * 18) / gcd

Print the GCD and LCM values exactly as shown

💡 Why This Matters

🌍 Real World

Finding GCD and LCM helps in tasks like dividing items evenly, scheduling repeating events, and simplifying fractions.

💼 Career

Understanding Euclidean algorithm and basic loops is essential for programming jobs that involve math, algorithms, and problem solving.

1

Create the two numbers

Create two integer variables called num1 and num2 with values 48 and 18 respectively.

DSA Java

# Your code here

Hint

Use int to declare variables and assign the exact numbers.

2

Store original value of num1

Create an integer variable called originalNum1 and set it equal to num1.

DSA Java

int num1 = 48;
int num2 = 18;
# Your code here

Hint

This helps keep the original value of num1 for later use.

3

Calculate GCD using Euclidean algorithm

Write a while loop that runs while num2 is not zero. Inside the loop, create an integer variable temp to store num2, then set num2 to num1 % num2, and finally set num1 to temp. This will calculate the GCD and store it in num1.

DSA Java

int num1 = 48;
int num2 = 18;
int originalNum1 = num1;
# Your code here

Hint

The Euclidean algorithm repeatedly replaces the larger number by the remainder until the remainder is zero.

4

Calculate and print GCD and LCM

Create an integer variable called gcd and set it equal to num1. Then create an integer variable called lcm and calculate it using the formula: (originalNum1 * 18) / gcd. Finally, print the GCD and LCM exactly as: System.out.println("GCD: " + gcd); and System.out.println("LCM: " + lcm);.

DSA Java

int num1 = 48;
int num2 = 18;
int originalNum1 = num1;

while (num2 != 0) {
    int temp = num2;
    num2 = num1 % num2;
    num1 = temp;
}
# Your code here

Hint

Remember to use the original value of num2 (which is 18) in the LCM formula.

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