Finding the Least Common Multiple (LCM) of two numbers is one of the most common Java coding interview questions.

This problem helps interviewers evaluate your understanding of:

• Loops
• Conditional statements
• Mathematical concepts
• Number theory
• Problem-solving skills

LCM is widely used in mathematics, fractions, scheduling problems, cyclic events, cryptography, and competitive programming.

---

What is LCM?

The Least Common Multiple (LCM) is the smallest positive integer that is exactly divisible by two or more numbers.

Unlike GCD, which finds the largest common divisor, LCM finds the smallest common multiple.

---

Example 1

Find the LCM of

4 and 6

Multiples of 4

4

8

12

16

20

24

Multiples of 6

6

12

18

24

30

Common Multiples

12

24

Smallest Common Multiple

12

Therefore

LCM(4,6) = 12

---

Example 2

Find the LCM of

8 and 10

Multiples of 8

8

16

24

32

40

48

Multiples of 10

10

20

30

40

50

First Common Multiple

40

Therefore

LCM(8,10) = 40

---

Example 3

Input

7

9

Multiples of 7

7

14

21

28

35

42

49

56

63

Multiples of 9

9

18

27

36

45

54

63

Output

63

---

Real Interview Question

Write a Java program to find the Least Common Multiple (LCM) of two numbers.

---

Understanding the Logic

Suppose

number1 = 6

number2 = 8

The LCM can never be smaller than the larger number.

Therefore,

Start = 8

Check whether

8

is divisible by both numbers.

If not,

increment the number.

Continue until a number is divisible by both.

---

Visual Representation

Input

6

8

Check

8

↓

9

↓

10

↓

11

↓

12

↓

13

↓

14

↓

15

↓

16

↓

17

↓

18

↓

19

↓

20

↓

21

↓

22

↓

23

↓

24

At

24

24 % 6 = 0

24 % 8 = 0

Therefore

LCM = 24

---

Brute Force Approach

The simplest solution is

• Find the larger number.
• Check whether it is divisible by both numbers.
• If not, increment it.
• Continue until both numbers divide it completely.
• Print the result.

---

Algorithm

Step 1

Read two numbers.

Step 2

Find the maximum.

int lcm = Math.max(number1, number2);

Step 3

Repeat forever.

Step 4

Check

lcm % number1 == 0

&&

lcm % number2 == 0

Step 5

If true,

print LCM.

Otherwise,

increment

lcm++;

Step 6

Repeat.

---

Dry Run

Input

4

6

Start

6

Current Number	Divisible by 4?	Divisible by 6?	LCM Found?
6	No	Yes	No
7	No	No	No
8	Yes	No	No
9	No	No	No
10	No	No	No
11	No	No	No
12	Yes	Yes	Yes

Output

12

---

Another Dry Run

Input

5

7

Start

7

Current Number	Divisible by 5?	Divisible by 7?
7	No	Yes
8	No	No
9	No	No
10	Yes	No
...	...	...
35	Yes	Yes

Output

35

---

Approach 1 — Using Iteration (Brute Force)

This is the easiest solution and is commonly asked in beginner-level interviews.

---

Complete Java Program

public class LCMExample {

    public static void main(String[] args) {

        int number1 = 6;
        int number2 = 8;

        int lcm = Math.max(number1, number2);

        while (true) {

            if (lcm % number1 == 0 &&
                lcm % number2 == 0) {

                break;

            }

            lcm++;

        }

        System.out.println("LCM = " + lcm);

    }

}

---

Output

LCM = 24

---

Step-by-Step Code Explanation

Step 1

Declare the two numbers.

int number1 = 6;
int number2 = 8;

Current values

6

8

---

Step 2

Find the larger number.

int lcm = Math.max(number1, number2);

Result

8

The LCM cannot be smaller than the larger number.

---

Step 3

Start an infinite loop.

while (true)

The loop continues until the LCM is found.

---

Step 4

Check divisibility.

if (lcm % number1 == 0 &&
    lcm % number2 == 0)

If both conditions are true,

the current number is the LCM.

---

Step 5

Otherwise,

increase the candidate.

lcm++;

The algorithm keeps checking the next number.

---

Step 6

Print the answer.

System.out.println("LCM = " + lcm);

Output

LCM = 24

---

Example Execution

Input

9

12

Largest Number

12

Numbers Checked

12

13

14

15

16

17

18

...

36

At

36

36 % 9 = 0

36 % 12 = 0

Output

LCM = 36

---

Input

3

5

Start

5

Numbers Checked

5

6

7

8

9

10

11

12

13

14

15

Output

LCM = 15

---

Why Does This Work?

The algorithm starts from the larger number because the Least Common Multiple cannot be smaller than either input.

It checks each number one by one until it finds the first number that is divisible by both inputs.

Since numbers are checked in increasing order, the first valid number is guaranteed to be the Least Common Multiple.

---

Advantages of This Approach

• Very easy to understand.
• Simple implementation.
• Excellent for beginners.
• No advanced mathematical concepts required.
• Frequently asked in entry-level coding interviews.

---

Drawbacks

Although this solution is easy to understand, it becomes very slow for large numbers because it checks many possible multiples.

Interviewers often ask follow-up questions such as:

• Can you solve it without checking every number?
• Can you use the GCD to find the LCM?
• Why is the GCD-based approach faster?
• Can you create a reusable method?
• What is the time complexity of both approaches?

In the next part, we'll cover:

• Optimized Approach Using GCD
• Euclidean Algorithm Integration
• Reusable Method
• Time and Space Complexity
• Comparison of All Approaches
• Common Interview Mistakes
• Frequently Asked Interview Questions
• Related Coding Problems
• Key Takeaways
• Interview Tips

Approach 2 — Using GCD (Optimized Approach)

The fastest and most commonly used method to find the Least Common Multiple (LCM) is by using the Greatest Common Divisor (GCD).

Instead of checking every possible multiple, we first calculate the GCD and then use the mathematical relationship between GCD and LCM.

---

Mathematical Formula

The relationship between GCD and LCM is

LCM(a, b) = (a × b) / GCD(a, b)

This formula is one of the most frequently asked interview concepts.

---

Understanding the Logic

Suppose

a = 12

b = 18

Find the GCD

GCD(12,18) = 6

Apply the formula

LCM

=

(12 × 18)

÷

6

=

216

÷

6

=

36

Therefore

LCM(12,18) = 36

---

Visual Representation

12

18

↓

Find GCD

↓

6

↓

Multiply Numbers

↓

12 × 18 = 216

↓

Divide by GCD

↓

216 ÷ 6 = 36

↓

Answer = 36

---

Algorithm

Step 1

Read two numbers.

Step 2

Find their GCD using the Euclidean Algorithm.

Step 3

Apply

LCM = (number1 * number2) / gcd;

Step 4

Print the result.

---

Dry Run

Input

15

20

Find GCD

GCD = 5

Calculation

LCM

=

15 × 20

÷

5

=

300

÷

5

=

60

Output

60

---

Another Dry Run

Input

9

12

GCD

3

Calculation

9 × 12

=

108

108 ÷ 3

=

36

Output

36

---

Java Program

public class LCMUsingGCD {

    public static void main(String[] args) {

        int number1 = 12;
        int number2 = 18;

        int a = number1;
        int b = number2;

        while (b != 0) {

            int remainder = a % b;

            a = b;

            b = remainder;

        }

        int gcd = a;

        int lcm = (number1 * number2) / gcd;

        System.out.println("LCM = " + lcm);

    }

}

---

Output

LCM = 36

---

Approach 3 — Using a Reusable Method

Reusable methods improve

• Readability
• Code reuse
• Maintainability
• Unit testing

---

Java Program

public class LCMMethod {

    static int gcd(int a, int b) {

        while (b != 0) {

            int remainder = a % b;

            a = b;

            b = remainder;

        }

        return a;

    }

    static int lcm(int a, int b) {

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

    }

    public static void main(String[] args) {

        System.out.println(lcm(24, 36));

    }

}

---

Output

72

---

Time Complexity

Brute Force

Operation	Complexity
Time	O(LCM) (Worst Case)
Space	O(1)

The brute-force approach may check many numbers before finding the LCM.

---

GCD-Based Solution

Operation	Complexity
Time	O(log(min(a,b)))
Space	O(1)

---

Comparison of All Approaches

Approach	Time	Space	Recommended
Brute Force	High	O(1)	Good for Beginners
Using GCD	O(log n)	O(1)	✅ Best for Interviews
Reusable Method	O(log n)	O(1)	Production Ready

---

Common Mistakes

Mistake 1

Starting from

1

instead of the larger number.

Wrong

int lcm = 1;

Correct

int lcm = Math.max(number1, number2);

---

Mistake 2

Using the wrong formula.

Wrong

LCM = GCD / (a × b)

Correct

LCM = (a × b) / GCD

---

Mistake 3

Finding GCD incorrectly.

Always use the Euclidean Algorithm.

while (b != 0) {

    int remainder = a % b;

    a = b;

    b = remainder;

}

---

Mistake 4

Integer overflow.

For very large numbers

number1 * number2

may overflow an int.

Use

long

for larger inputs.

Example

long lcm = ((long) number1 * number2) / gcd;

---

Mistake 5

Ignoring zero.

If either number is

0

then

LCM = 0

Handle this case before applying the formula.

Example

if (number1 == 0 || number2 == 0) {

    return 0;

}

---

Interview Follow-up Questions

Q1. Explain the relationship between GCD and LCM.

Q2. Why is the GCD-based solution faster?

Q3. Find the LCM of an array.

Q4. Find the GCD and LCM together.

Q5. Find the LCM of three numbers.

Q6. Implement the Euclidean Algorithm.

Q7. What happens if one number is zero?

Q8. Can LCM overflow an int?

Q9. Compare brute-force and optimized approaches.

Q10. Where is LCM used in real-world applications?

---

Related Coding Problems

• GCD (HCF)
• Prime Number
• Co-prime Numbers
• Decimal to Binary
• Binary to Decimal
• Factorial
• Fibonacci Series
• Power of a Number

---

Key Takeaways

• The Least Common Multiple (LCM) is the smallest number divisible by both inputs.
• The brute-force approach checks multiples one by one.
• The optimized approach uses the mathematical relationship between GCD and LCM.
• The formula

LCM(a,b) = (a × b) / GCD(a,b)

is the preferred interview solution.

• The Euclidean Algorithm makes the GCD calculation extremely efficient.
• The optimized solution runs in O(log n) time with O(1) extra space.
• Handle special cases such as zero and potential integer overflow when implementing production-quality code.

---

Interview Tip

If an interviewer asks:

"Write a Java program to find the LCM of two numbers."

Start by explaining the brute-force approach briefly, then introduce the optimized solution using the GCD formula:

LCM(a,b) = (a × b) / GCD(a,b)

Implement the Euclidean Algorithm to compute the GCD efficiently, and then calculate the LCM. Mention the O(log n) time complexity, explain why this approach is significantly faster than checking multiples one by one, and discuss handling edge cases such as zero values and integer overflow. Demonstrating both the straightforward and optimized solutions highlights strong algorithmic thinking and practical Java programming skills.