Code Logo

Least Common Multiple

Published at25 Jul 2026
Created by
Number Theory Easy 2 views
Like0

Given two non-negative integers a and b, compute their least common multiple (LCM). The LCM is the smallest positive integer that is divisible by both a and b.

For example, LCM(4, 6) = 12 because 12 is the smallest number divisible by both 4 and 6. LCM(7, 3) = 21. LCM(0, 5) = 0 (zero is divisible by any number, and by convention LCM with zero is 0). LCM(12, 8) = 24.

The LCM is closely related to the GCD (greatest common divisor) through the formula: LCM(a, b) = |a × b| / GCD(a, b). This relationship means that if you can compute the GCD (using the Euclidean algorithm), you can compute the LCM efficiently without trial division.

Applications of LCM include adding and subtracting fractions (finding a common denominator), scheduling problems (when will two recurring events coincide?), and gear ratio calculations in mechanical engineering.

When implementing, be careful about overflow: a × b can overflow before division by GCD brings it back. One trick is to divide one number by GCD first, then multiply: a / GCD(a, b) * b. This keeps intermediate values smaller. Edge cases include either number being 0 (return 0) and both numbers being equal (the LCM equals either number).

Example Input & Output

Example 1
Input
7,5
Output
35
Explanation

Prime pair

Example 2
Input
17,17
Output
17
Explanation

Same numbers

Example 3
Input
12,8
Output
24
Explanation

LCM of 12 and 8 is 24

Example 4
Input
0,5
Output
0
Explanation

Zero

Example 5
Input
4,6
Output
12
Explanation

LCM of 4 and 6 is 12

Algorithm Flow

Recommendation Algorithm Flow for Least Common Multiple
Recommendation Algorithm Flow for Least Common Multiple

Solution Approach

Use the formula LCM(a, b) = |a × b| / GCD(a, b), computing GCD with the Euclidean algorithm.

function solution(a, b) {
  if (a === 0 || b === 0) return 0;
  var gcd = function(x, y) {
    while (y !== 0) { var t = y; y = x % y; x = t; }
    return x;
  };
  return (a / gcd(a, b)) * b;
}

First check if either number is 0 and return 0. Then compute the GCD using the Euclidean algorithm. Finally, compute (a / gcd) * b instead of (a * b) / gcd to avoid integer overflow. Dividing a by the GCD first reduces the magnitude of the intermediate value.

For example, LCM(12, 8): GCD(12, 8) = 4. (12 / 4) * 8 = 3 * 8 = 24. This matches the expected result. LCM(7, 3): GCD(7, 3) = 1. (7 / 1) * 3 = 7 * 3 = 21.

Time complexity is O(log min(a, b)) due to the Euclidean algorithm. Space complexity is O(1).

Best Answers

java
class Solution {
    public int solution(int a, int b) {
        if(a==0||b==0)return 0;int x=a,y=b;
        while(y!=0){int t=y;y=x%y;x=t;}
        return Math.abs(a*b)/x;
    }
}