Find the LCM of Two Numbers
Solve this ProblemEasy10 min
Topics
BasicsLoopsMath
Companies
TCSInfosysWipro
Given two positive integers
a and b, return their least common multiple (LCM) — the smallest positive number divisible by both.
The brute-forceBrute ForceChecking multiples of the larger number one at a time until one is also divisible by the smaller number. approach searches directly for the answer. The GCD formulaLCM via GCDThe identity LCM(a, b) × GCD(a, b) = a × b — rearranged to LCM(a, b) = (a / GCD(a, b)) × b, so the fast Euclidean GCD does all the real work. approach skips the search entirely: since a × b always equals LCM × GCD, finding the GCD first (fast, via Find the GCD of Two Numbers) hands over the LCM with one division and one multiplication.
Test Case 1:
Input:a = 4, b = 6
Output:12
Explanation:12 is the smallest number divisible by both 4 and 6.
Test Case 2:
Input:a = 7, b = 13
Output:91
Explanation:Two numbers with no common factor — their LCM is just their product.
Test Case 3:
Input:a = 5, b = 5
Output:5
Explanation:A number is always its own LCM with itself.
Constraints
- ◆
1 ≤ a ≤ 10000 - ◆
1 ≤ b ≤ 10000
Try the Dry Run
Approach & Solutions
Brute Force — Check Every Multiple of the Larger NumberBrute
The LCM must be a multiple of the larger of the two numbers, and it's never bigger than a × b. So check multiples of the larger number — larger, 2×larger, 3×larger, ... — and return the first one that's also divisible by the smaller number.
Time
O((a × b) / max(a, b))Space
O(1)Java
1class Solution {
2 public int findLCM(int a, int b) {
3 int larger = Math.max(a, b);
4 int smaller = Math.min(a, b);
5 for (int candidate = larger; ; candidate += larger) {
6 if (candidate % smaller == 0) {
7 return candidate;
8 }
9 }
10 }
11}Using the GCD — LCM = (a × b) / GCD(a, b)Optimal
There's a direct formula connecting LCM and GCD: their product always equals a × b. Finding the GCD with the fast Euclidean algorithm, then dividing, gets the LCM without any searching — dividing by the GCD first (before multiplying) also keeps the intermediate value smaller and safer from overflow.
Time
O(log(min(a, b)))Space
O(1)Java
1class Solution {
2 public int findLCM(int a, int b) {
3 int gcd = findGCD(a, b);
4 return (a / gcd) * b;
5 }
6
7 private int findGCD(int a, int b) {
8 while (b != 0) {
9 int temp = b;
10 b = a % b;
11 a = temp;
12 }
13 return a;
14 }
15}