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 <= 105, 1 <= arr[i] <= 105.
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> |
4
Time Complexity: O(N2)
Auxiliary Space: O(log(Ai)), where Ai 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> |
4
Time Complexity: O((N + M) * log(M))
Auxiliary Space: O(M) where M is the maximum element in the array.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!