easyNumber ProblemsJava

Find the LCM of Two Numbers

Compute the least common multiple of two integers using their GCD.

Quick Answer

The least common multiple relates to the greatest common divisor by lcm(a, b) = a * b / gcd(a, b). Compute the GCD with the Euclidean algorithm, then divide before multiplying (a / gcd * b) to reduce the chance of overflow. For 4 and 6 the GCD is 2, so the LCM is 12.

Problem Statement

The least common multiple (LCM) of two integers is the smallest positive number that is a multiple of both. The cleanest way to compute it uses the identity lcm(a, b) = a * b / gcd(a, b), where gcd is the greatest common divisor.

Given two positive integers, return their LCM. Compute the GCD first (Euclidean algorithm), then combine. Divide by the GCD before multiplying to keep intermediate values smaller and avoid overflow.

Input: Two integers a and b.

Output: The least common multiple of a and b.

Examples

Example 1
Input:  4, 6
Output: 12

gcd(4, 6) = 2, so lcm = 4 / 2 * 6 = 2 * 6 = 12; 12 is the smallest multiple of both.

Example 2
Input:  5, 7
Output: 35

5 and 7 are coprime (gcd 1), so their LCM is simply 5 * 7 = 35.

Constraints

  • a and b are positive and fit in a 32-bit int
  • lcm(a, 0) is defined as 0 here

Think Before You Code

Reveal the questions to ask yourself first
  • How are the LCM and GCD of two numbers related?
  • Why divide by the GCD before multiplying rather than after?
  • What should the LCM be if one of the inputs is 0?

Hints

Open them one at a time — try after each before revealing the next.

Hint 1
Use the identity lcm(a, b) = a * b / gcd(a, b) so you never scan multiples one by one.
Hint 2
Compute the GCD with the Euclidean algorithm, then plug it into the formula.
Hint 3
Rearrange to a / gcd * b to keep the intermediate product small and reduce overflow risk; use long for safety.

Approach

Reveal the step-by-step approach

Derive the LCM from the GCD.

  1. If either input is 0, return 0.
  2. Compute g = gcd(a, b) using the Euclidean algorithm.
  3. Return (a / g) * b (dividing first keeps the product smaller).

Because a / g is an exact division, the result is still correct while the intermediate value stays well below a * b, lowering the overflow risk.

Dry Run

Walk through the example step by step

Computing lcm(4, 6):

step                 | value
---------------------+------
gcd(4, 6)            | 2
a / gcd = 4 / 2      | 2
(a / gcd) * b = 2*6  | 12

Least common multiple: 12

Solution

Reveal the full Java solution
public class LcmOfTwoNumbers {
    public static long lcm(int a, int b) {
        if (a == 0 || b == 0) {
            return 0;
        }
        int g = gcd(a, b);
        return (long) (Math.abs(a) / g) * Math.abs(b);
    }

    private static int gcd(int a, int b) {
        a = Math.abs(a);
        b = Math.abs(b);
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }

    public static void main(String[] args) {
        System.out.println(lcm(4, 6)); // 12
        System.out.println(lcm(5, 7)); // 35
    }
}

Because gcd(a, b) divides a exactly, a / g is a whole number, so (a / g) * b equals a * b / g without ever forming the larger product a * b. Casting to long before the final multiply gives extra headroom so big inputs do not overflow.

Time: O(log(min(a, b))) — dominated by the GCD stepSpace: O(1)

Common Mistakes

  • Computing a * b first and overflowing before dividing by the GCD.
  • Looping through multiples to find the LCM, which is far slower than using the GCD.

Edge Cases to Test

  • lcm with a 0 input returns 0.
  • Coprime inputs (gcd 1) give the LCM as the plain product a * b.

Interview Follow-Ups

  • How would you compute the LCM of an entire array of numbers?
  • How would you prove that lcm(a, b) * gcd(a, b) always equals a * b?

Practising for Java interviews?

CodeBegun's Java Full Stack with AI program builds this problem-solving muscle with mentor review and mock interviews.

Explore the Java Full Stack program →
Chat with us