Skip to main content
CodePeet

CodePeet 444 Complete DSA Sheet

LCM of Two Numbers

Try it yourself
EasyProblem

Description

Given two positive integers a and b, return their least common multiple: the smallest positive number that both of them divide.

Examples

Example 1

Input: a = 4, b = 6

Output: 12

Explanation: The multiples of 6 are 6, 12, 18, ...; 12 is the first one 4 also divides.

Example 2

Input: a = 5, b = 7

Output: 35

Explanation: 5 and 7 share no factor, so their least common multiple is their product, 35.

Example 3

Input: a = 6, b = 6

Output: 6

Explanation: A number's least common multiple with itself is the number.

Example 4

Input: a = 1, b = 10

Output: 10

Explanation: 1 divides everything, so the answer is 10.

Constraints

  • 1 ≤ a, b ≤ 10^6

Editorial

Brute Force - Walk the Multiples

Intuition

The least common multiple is a multiple of the larger number, so try those in order, the larger number, then twice it, and so on, and stop at the first one the smaller number divides.

Step-by-Step Explanation

Let's trace Example 1, a = 4, b = 6:

  1. Start at m = 6.
  2. 6 % 4 = 2: not a multiple of 4, so add 6.
  3. 12 % 4 = 0: 12 is a multiple of both. Return 12.

Walk the Multiples — The multiples of 6 tried in turn until 4 divides one.

Algorithm

  1. Let big be the larger number and small the smaller.
  2. Start m at big; while small doesn't divide m, add big to m.
  3. Return m.

Code

class Solution {
public:
    long long lcm(int a, int b) {
        long long big = max(a, b), small = min(a, b);
        long long m = big;
        while (m % small != 0) m += big;    // the next multiple of the larger number
        return m;
    }
};

class Solution:
    def lcm(self, a: int, b: int) -> int:
        big, small = max(a, b), min(a, b)
        m = big
        while m % small != 0:               # the next multiple of the larger number
            m += big
        return m

class Solution {
    public long lcm(int a, int b) {
        long big = Math.max(a, b), small = Math.min(a, b);
        long m = big;
        while (m % small != 0) m += big;    // the next multiple of the larger number
        return m;
    }
}

var lcm = function(a, b) {
    const big = Math.max(a, b), small = Math.min(a, b);
    let m = big;
    while (m % small !== 0) m += big;       // the next multiple of the larger number
    return m;
};

Complexity Analysis

Time Complexity: O(min(a, b))

The answer is at most a × b, so m takes at most small steps.

Space Complexity: O(1)

Two numbers.

Why This Approach Is Not Efficient

When the two numbers share no factor, the answer is their product, and the walk takes small steps. For the two largest primes below 10^6, 999,983 and 999,979, it took 158 ms for that one pair in Python on our judge. The tests have 60 pairs like it, and it ran out of time in Python.

There's a shortcut. a × b counts every shared factor twice, once from each number; dividing by the greatest common divisor, gcd(a, b), counts it once. So lcm(a, b) = a / gcd(a, b) × b, and Euclid's algorithm finds the gcd in a handful of steps.

Optimal Approach - Through the GCD

Intuition

Euclid's algorithm rests on one fact: gcd(x, y) = gcd(y, x % y). Each step makes the pair smaller, and when y reaches 0, x is the gcd.

Then divide before multiplying, a / gcd × b, so nothing gets bigger than the answer. In Java and C++ the answer reaches 10^12, so the multiplication is done in a long (long long in C++).

Step-by-Step Explanation

Let's trace the same example, a = 4, b = 6:

  1. (4, 6) becomes (6, 4 % 6) = (6, 4).
  2. (6, 4) becomes (4, 6 % 4) = (4, 2).
  3. (4, 2) becomes (2, 4 % 2) = (2, 0).
  4. y is 0: the gcd is 2. The least common multiple is 4 / 2 × 6 = 12.

Euclid's Pair — The pair (x, y) becomes (y, x % y) until y is 0; then x is the gcd.

Algorithm

  1. Find g = gcd(a, b): while y isn't 0, replace (x, y) with (y, x % y).
  2. Return a / g * b.

Code

For 999,983 and 999,979 it took 29 ms in Python on our judge.

class Solution {
public:
    long long lcm(int a, int b) {
        int x = a, y = b;
        while (y != 0) {                    // Euclid: gcd(x, y) = gcd(y, x % y)
            int r = x % y;
            x = y;
            y = r;
        }
        return (long long) (a / x) * b;     // long long: the result reaches 10^12
    }
};

class Solution:
    def lcm(self, a: int, b: int) -> int:
        x, y = a, b
        while y:                            # Euclid: gcd(x, y) = gcd(y, x % y)
            x, y = y, x % y
        return a // x * b

class Solution {
    public long lcm(int a, int b) {
        int x = a, y = b;
        while (y != 0) {                    // Euclid: gcd(x, y) = gcd(y, x % y)
            int r = x % y;
            x = y;
            y = r;
        }
        return (long) (a / x) * b;          // long: the result reaches 10^12
    }
}

var lcm = function(a, b) {
    let x = a, y = b;
    while (y !== 0) [x, y] = [y, x % y];    // Euclid: gcd(x, y) = gcd(y, x % y)
    return a / x * b;
};

Complexity Analysis

Time Complexity: O(log min(a, b))

Every two of Euclid's steps at least halve the smaller number.

Space Complexity: O(1)

Two numbers.

Common Mistakes

Each of these looks right on a quick read, and the tests still reject it. The outputs below come from running the code.

Multiplying as ints first. return a * b / x;

On a = 999983, b = 999979 it returns -765379611 in Java; the answer is 999962000357. a * b of two ints is worked out as an int, and near 10^6 × 10^6 = 10^12 that wraps around long before the division, even though the result is returned as a long. Divide first, or cast to long before multiplying.

Returning the product. return a * b

On a = 4, b = 6 it returns 24; the answer is 12. a × b is a common multiple, but not the least when a and b share a factor: 4 × 6 = 24, while 12 will do. Dividing by gcd(a, b) removes the shared part.

Where This Pattern Is Taught

This problem practises a loop with % that shrinks a pair of numbers, and a product kept in a 64-bit type. It's taught in Python for DSA, Java for DSA, C++ for DSA and JavaScript for DSA.