GCD and LCM Euclidean Algorithm in DSA Java - Execution Trace

Concept Flow - GCD and LCM Euclidean Algorithm

Start with two numbers a, b

↓

Check if b == 0?

Yes→GCD is a

No↓

Calculate a % b

↓

Set a = b, b = a % b

↓

Repeat until b == 0

↓

Calculate LCM = (original_a * original_b) / GCD

Start with two numbers, repeatedly replace a by b and b by a mod b until b is zero. The last non-zero a is the GCD. Then use GCD to find LCM.

Execution Sample

DSA Java

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

This code finds the greatest common divisor (GCD) of two numbers using the Euclidean algorithm.

Execution Table

Step	Operation	a	b	a % b	Action	GCD So Far
1	Start	48	18	N/A	Check b != 0	N/A
2	Calculate a % b	48	18	12	Set a=18, b=12	N/A
3	Calculate a % b	18	12	6	Set a=12, b=6	N/A
4	Calculate a % b	12	6	0	Set a=6, b=0	N/A
5	b == 0	6	0	N/A	Stop, GCD=6	6

💡 Loop stops when b becomes 0; last a is GCD.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	Final
a	48	18	12	6	6
b	18	12	6	0	0
a % b	N/A	12	6	0	N/A

Key Moments - 3 Insights

Why do we replace a with b and b with a % b instead of other values?

Because the Euclidean algorithm relies on the fact that GCD(a, b) = GCD(b, a % b). This is shown in steps 2-4 of the execution_table where a and b update accordingly.

Why does the loop stop when b becomes zero?

When b is zero, a holds the GCD. This is shown in step 5 where b=0 and the algorithm stops returning a=6.

How is LCM calculated after finding GCD?

LCM is calculated using the formula LCM = (original_a * original_b) / GCD. This uses the GCD found at the end of the Euclidean algorithm.

Visual Quiz - 3 Questions

Look at the execution_table, what is the value of 'a' after step 3?

A 18

B 6

C 12

D 48

💡 Hint

Check the 'a' column in the execution_table row for step 3.

At which step does the condition b != 0 become false?

A Step 4

B Step 5

C Step 3

D Step 2

💡 Hint

Look at the 'b' value in execution_table; when b=0, loop stops.

If the initial numbers were 30 and 12, how would the first 'a % b' value change in the execution_table?

A 6

B 0

C 18

D 12

💡 Hint

Calculate 30 % 12 to find the first remainder.

Concept Snapshot

Euclidean Algorithm for GCD:
- Repeat: a, b = b, a % b until b == 0
- GCD is last non-zero a
- LCM = (original_a * original_b) / GCD
- Efficient and fast for large numbers
- Uses remainder to reduce problem size

Full Transcript

The Euclidean algorithm finds the greatest common divisor (GCD) of two numbers by repeatedly replacing the larger number with the remainder of dividing the larger by the smaller. This continues until the remainder is zero. The last non-zero number is the GCD. Then, the least common multiple (LCM) can be found by dividing the product of the original numbers by the GCD. The execution table shows step-by-step how the values of a and b change, and the variable tracker records these changes. Key moments clarify why the algorithm updates variables as it does and when it stops. The visual quiz tests understanding of these steps.

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