Minimum LCM of all pairs in a given array

0 0 10 minutes read

Given an array arr[] of size N, the task is to find the minimum LCM (Least Common Multiple) of all unique pairs in the given array, where 1 <= N <= 10⁵, 1 <= arr[i] <= 10⁵.

Examples:

Input: arr[] = {2, 4, 3}
Output: 4
Explanation
LCM (2, 4) = 4
LCM (2, 3) = 6
LCM (4, 3) = 12
Minimum possible LCM is 4.

Input: arr [] ={1, 5, 2, 2, 6}
Output: 2

Naive Approach

Generate all possible pairs and compute LCM for every unique pair.
Find the minimum LCM from all unique pairs.

Below is the implementation of the above approach:

C++

// C++ program to find
// minimum possible lcm
// from any pair
 
#include <bits/stdc++.h>
using namespace std;
 
// function to compute
// GCD of two numbers
int gcd(int a, int b)
{
    if (b == 0)
        return a;
    return gcd(b, a % b);
}
 
// function that return
// minimum possible lcm
// from any pair
int minLCM(int arr[], int n)
{
    int ans = INT_MAX;
    for (int i = 0; i < n; i++) {
 
        // fix the ith element and
        // iterate over all the array
        // to find minimum LCM
        for (int j = i + 1; j < n; j++) {
 
            int g = gcd(arr[i], arr[j]);
            int lcm = arr[i] / g * arr[j];
            ans = min(ans, lcm);
        }
    }
 
    return ans;
}
 
// Driver code
int main()
{
    int arr[] = { 2, 4, 3, 6, 5 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << minLCM(arr, n) << endl;
    return 0;
}

Java

// Java program to find minimum
// possible lcm from any pair
import java.io.*; 
import java.util.*; 
 
class GFG { 
     
// Function to compute
// GCD of two numbers
static int gcd(int a, int b)
{ 
    if (b == 0)
        return a;
    return gcd(b, a % b);
} 
 
// Function that return minimum
// possible lcm from any pair
static int minLCM(int arr[], int n)
{
    int ans = Integer.MAX_VALUE;
     
    for(int i = 0; i < n; i++) 
    {
         
       // Fix the ith element and
       // iterate over all the array
       // to find minimum LCM
       for(int j = i + 1; j < n; j++) 
       {
          int g = gcd(arr[i], arr[j]);
          int lcm = arr[i] / g * arr[j];
          ans = Math.min(ans, lcm);
       }
    }
    return ans;
}
     
// Driver code 
public static void main(String[] args) 
{ 
    int arr[] = { 2, 4, 3, 6, 5 };
    int n = arr.length;
     
    System.out.println(minLCM(arr,n)); 
} 
} 
 
// This code is contributed by coder001

Python3

# Python3 program to find minimum 
# possible lcm from any pair 
import sys
 
# Function to compute 
# GCD of two numbers 
def gcd(a, b):
     
    if (b == 0):
        return a;
    return gcd(b, a % b);
 
# Function that return minimum 
# possible lcm from any pair
def minLCM(arr, n):
     
    ans = 1000000000;
    for i in range(n):
 
        # Fix the ith element and 
        # iterate over all the 
        # array to find minimum LCM
        for j in range(i + 1, n):
             
            g = gcd(arr[i], arr[j]);
            lcm = arr[i] / g * arr[j];
            ans = min(ans, lcm);
             
    return ans;
 
# Driver code
arr = [ 2, 4, 3, 6, 5 ];
 
print(minLCM(arr, 5))
 
# This code is contributed by grand_master

C#

// C# program to find minimum
// possible lcm from any pair
using System;
class GFG{ 
     
// Function to compute
// GCD of two numbers
static int gcd(int a, int b)
{ 
    if (b == 0)
        return a;
    return gcd(b, a % b);
} 
 
// Function that return minimum
// possible lcm from any pair
static int minLCM(int []arr, int n)
{
    int ans = Int32.MaxValue;
     
    for(int i = 0; i < n; i++) 
    {
         
    // Fix the ith element and
    // iterate over all the array
    // to find minimum LCM
    for(int j = i + 1; j < n; j++) 
    {
        int g = gcd(arr[i], arr[j]);
        int lcm = arr[i] / g * arr[j];
        ans = Math.Min(ans, lcm);
    }
    }
    return ans;
}
     
// Driver code 
public static void Main() 
{ 
    int []arr = { 2, 4, 3, 6, 5 };
    int n = arr.Length;
     
    Console.Write(minLCM(arr,n)); 
} 
} 
 
// This code is contributed by Akanksha_Rai

Javascript

<script>
 
    // Javascript program to find
    // minimum possible lcm
    // from any pair
     
    // function to compute
    // GCD of two numbers
    function gcd(a, b)
    {
        if (b == 0)
            return a;
        return gcd(b, a % b);
    }
 
    // function that return
    // minimum possible lcm
    // from any pair
    function minLCM(arr, n)
    {
        let ans = Number.MAX_VALUE;
        for (let i = 0; i < n; i++) {
 
            // fix the ith element and
            // iterate over all the array
            // to find minimum LCM
            for (let j = i + 1; j < n; j++) {
 
                let g = gcd(arr[i], arr[j]);
                let lcm = arr[i] / g * arr[j];
                ans = Math.min(ans, lcm);
            }
        }
 
        return ans;
    }
     
    let arr = [ 2, 4, 3, 6, 5 ];
    let n = arr.length;
    document.write(minLCM(arr, n));
 
 
</script>

Output:

Time Complexity: O(N²)
Auxiliary Space: O(log(A_i)), where A_i is the second maximum element in the array.

Efficient Approach: This approach depends upon the formula:

Product of two number = LCM of two number * GCD of two number

In the formula of LCM, the denominator is the GCD of two numbers, and the GCD of two numbers will never be greater than the number itself.
So for a fixed GCD, find the smallest two multiples of that fixed GCD that is present in the given array.
Store only the smallest two multiples of each GCD because choosing a bigger multiple of GCD that is present in the array, no matter what, it will never give the minimum answer.
Finally, use a sieve to find the minimum two number that is the multiple of the chosen GCD.

Below is the implementation of the above approach:

C++

// C++ program to find the
// pair having minimum LCM
 
#include <bits/stdc++.h>
using namespace std;
 
// function that return
// pair having minimum LCM
int minLCM(int arr[], int n)
{
    int mx = 0;
    for (int i = 0; i < n; i++) {
 
        // find max element in the array as
        // the gcd of two elements from the
        // array can't greater than max element.
        mx = max(mx, arr[i]);
    }
 
    // created a 2D array to store minimum
    // two multiple of any particular i.
    vector<vector<int> > mul(mx + 1);
 
    for (int i = 0; i < n; i++) {
        if (mul[arr[i]].size() > 1) {
            // we already found two
            // smallest multiple
            continue;
        }
        mul[arr[i]].push_back(arr[i]);
    }
 
    // iterating over all gcd
    for (int i = 1; i <= mx; i++) {
 
        // iterating over its multiple
        for (int j = i + i; j <= mx; j += i) {
 
            if (mul[i].size() > 1) {
 
                // if we already found the
                // two smallest multiple of i
                break;
            }
            for (int k : mul[j]) {
                if (mul[i].size() > 1)
                    break;
                mul[i].push_back(k);
            }
        }
    }
 
    int ans = INT_MAX;
    for (int i = 1; i <= mx; i++) {
 
        if (mul[i].size() <= 1)
            continue;
 
        // choosing smallest two multiple
        int a = mul[i][0], b = mul[i][1];
 
        // calculating lcm
        int lcm = (a * b) / i;
 
        ans = min(ans, lcm);
    }
 
    // return final answer
    return ans;
}
 
// Driver code
int main()
{
    int arr[] = { 2, 4, 3, 6, 5 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << minLCM(arr, n) << endl;
    return 0;
}

Java

// Java program to find the
// pair having minimum LCM
import java.util.Vector;
class GFG{
 
// Function that return
// pair having minimum LCM
static int minLCM(int arr[], 
                  int n)
{
  int mx = 0;
  for (int i = 0; i < n; i++) 
  {
    // Find max element in the 
    // array as the gcd of two 
    // elements from the array 
    // can't greater than max element.
    mx = Math.max(mx, arr[i]);
  }
 
  // Created a 2D array to store minimum
  // two multiple of any particular i.
  Vector<Integer> []mul = new Vector[mx + 1];
   
  for (int i = 0; i < mul.length; i++)
    mul[i] = new Vector<Integer>();
  for (int i = 0; i < n; i++) 
  {
    if (mul[arr[i]].size() > 1) 
    {
      // We already found two
      // smallest multiple
      continue;
    }
    mul[arr[i]].add(arr[i]);
  }
 
  // Iterating over all gcd
  for (int i = 1; i <= mx; i++) 
  {
    // Iterating over its multiple
    for (int j = i + i; j <= mx; j += i) 
    {
      if (mul[i].size() > 1) 
      {
        // If we already found the
        // two smallest multiple of i
        break;
      }      
      for (int k : mul[j]) 
      {
        if (mul[i].size() > 1)
          break;
        mul[i].add(k);
      }
    }
  }
 
  int ans = Integer.MAX_VALUE;
  for (int i = 1; i <= mx; i++) 
  {
    if (mul[i].size() <= 1)
      continue;
 
    //  Choosing smallest
    // two multiple
    int a = mul[i].get(0), 
        b = mul[i].get(1);
 
    // Calculating lcm
    int lcm = (a * b) / i;
 
    ans = Math.min(ans, lcm);
  }
 
  // Return final answer
  return ans;
}
 
// Driver code
public static void main(String[] args)
{
  int arr[] = {2, 4, 3, 6, 5};
  int n = arr.length;
  System.out.print(minLCM(arr, n) + "\n");
}
}
 
// This code is contributed by shikhasingrajput

Python3

# Python3 program to find the
# pair having minimum LCM
import sys
 
# function that return
# pair having minimum LCM
def minLCM(arr, n) :
    mx = 0
    for i in range(n) :
 
        # find max element in the array as
        # the gcd of two elements from the
        # array can't greater than max element.
        mx = max(mx, arr[i])
 
    # created a 2D array to store minimum
    # two multiple of any particular i.
    mul = [[] for i in range(mx + 1)]
 
    for i in range(n) :
        if (len(mul[arr[i]]) > 1) :
           
            # we already found two
            # smallest multiple
            continue
         
        mul[arr[i]].append(arr[i])
 
    # iterating over all gcd
    for i in range(1, mx + 1) :
 
        # iterating over its multiple
        for j in range(i + i, mx + 1, i) :
 
            if (len(mul[i]) > 1) :
 
                # if we already found the
                # two smallest multiple of i
                break
     
            for k in mul[j] :
                if (len(mul[i]) > 1) :
                    break
                mul[i].append(k)
 
    ans = sys.maxsize
    for i in range(1, mx + 1) :
        if (len(mul[i]) <= 1) :
            continue
 
        # choosing smallest two multiple
        a, b = mul[i][0], mul[i][1]
 
        # calculating lcm
        lcm = (a * b) // i
        ans = min(ans, lcm)
 
    # return final answer
    return ans
 
# Driver code
arr = [ 2, 4, 3, 6, 5 ]
n = len(arr) 
print(minLCM(arr, n))
 
# This code is contributed by divyesh072019

C#

// C# program to find the
// pair having minimum LCM
using System;
using System.Collections.Generic;
class GFG{
 
// Function that return
// pair having minimum LCM
static int minLCM(int []arr, 
                  int n)
{
  int mx = 0;
   
  for (int i = 0; i < n; i++) 
  {
    // Find max element in the 
    // array as the gcd of two 
    // elements from the array 
    // can't greater than max element.
    mx = Math.Max(mx, arr[i]);
  }
 
  // Created a 2D array to store minimum
  // two multiple of any particular i.
  List<int> []mul = new List<int>[mx + 1];
   
  for (int i = 0; i < mul.Length; i++)
    mul[i] = new List<int>();
   
  for (int i = 0; i < n; i++) 
  {
    if (mul[arr[i]].Count > 1) 
    {
      // We already found two
      // smallest multiple
      continue;
    }
    mul[arr[i]].Add(arr[i]);
  }
 
  // Iterating over all gcd
  for (int i = 1; i <= mx; i++) 
  {
    // Iterating over its multiple
    for (int j = i + i; j <= mx; j += i) 
    {
      if (mul[i].Count > 1) 
      {
        // If we already found the
        // two smallest multiple of i
        break;
      }      
      foreach (int k in mul[j]) 
      {
        if (mul[i].Count > 1)
          break;
        mul[i].Add(k);
      }
    }
  }
 
  int ans = int.MaxValue;
  for (int i = 1; i <= mx; i++) 
  {
    if (mul[i].Count <= 1)
      continue;
 
    //  Choosing smallest
    // two multiple
    int a = mul[i][0], 
        b = mul[i][1];
 
    // Calculating lcm
    int lcm = (a * b) / i;
 
    ans = Math.Min(ans, lcm);
  }
 
  // Return readonly answer
  return ans;
}
 
// Driver code
public static void Main(String[] args)
{
  int []arr = {2, 4, 3, 6, 5};
  int n = arr.Length;
  Console.Write(minLCM(arr, n) + "\n");
}
}
 
// This code is contributed by Princi Singh

Javascript

<script>
 
// Javascript program to find the
// pair having minimum LCM
 
// function that return
// pair having minimum LCM
function minLCM(arr, n)
{
    var mx = 0;
    for(var i = 0; i < n; i++)
    {
         
        // Find max element in the array as
        // the gcd of two elements from the
        // array can't greater than max element.
        mx = Math.max(mx, arr[i]);
    }
 
    // Created a 2D array to store minimum
    // two multiple of any particular i.
    var mul = Array.from(Array(mx + 1), () => Array());
 
    for(var i = 0; i < n; i++) 
    {
        if (mul[arr[i]].length > 1)
        {
             
            // We already found two
            // smallest multiple
            continue;
        }
        mul[arr[i]].push(arr[i]);
    }
 
    // Iterating over all gcd
    for(var i = 1; i <= mx; i++) 
    {
         
        // Iterating over its multiple
        for(var j = i + i; j <= mx; j += i)
        {
            if (mul[i].length > 1)
            {
                 
                // If we already found the
                // two smallest multiple of i
                break;
            }
            mul[j].forEach(k => {
                 
                if (mul[i].length <= 1)
                {
                    mul[i].push(k);
                }
            });
        }
    }
 
    var ans = 1000000000;
    for(var i = 1; i <= mx; i++) 
    {
        if (mul[i].length <= 1)
            continue;
 
        // Choosing smallest two multiple
        var a = mul[i][0], b = mul[i][1];
 
        // Calculating lcm
        var lcm = (a * b) / i;
 
        ans = Math.min(ans, lcm);
    }
 
    // Return final answer
    return ans;
}
 
// Driver code
var arr = [ 2, 4, 3, 6, 5 ];
var n = arr.length;
 
document.write( minLCM(arr, n) + "<br>");
 
// This code is contributed by itsok
 
</script>

Output:

Time Complexity: O((N + M) * log(M))
Auxiliary Space: O(M) where M is the maximum element in the array.

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!