Maximum LCM among all pairs (i, j) from the given Array
Given an array arr[], the task is to find the maximum LCM when the elements of the array are taken in pairs.
Examples:
Input: arr[] = {17, 3, 8, 6}
Output: 136
Explanation:
Respective Pairs with their LCM are:
{8, 17} has LCM 136,
{3, 17} has LCM 51,
{6, 17} has LCM 102,
{3, 8} has LCM 24,
{3, 6} has LCM 6, and
{6, 8} has LCM 24.
Maximum LCM among these =136.Input: array[] = {1, 8, 12, 9}
Output: 72
Explanation:
72 is the highest LCM among all the pairs of the given array.
Naive Approach: Use two loops to generate all possible pairs of elements of the array and calculate LCM of them. Update the LCM whenever we get a higher value.
Time Complexity: O(N2)
Below is the implementation of the above approach:
C++
// C++ implementation to find the maximum // LCM of pairs in an array #include <bits/stdc++.h> using namespace std; // Function comparing all LCM pairs int maxLcmOfPairs( int arr[], int n) { // To store the highest LCM int maxLCM = -1; // To generate all pairs from array for ( int i = 0; i < n; i++) { for ( int j = i + 1; j < n; j++) { // Find LCM of the pair // Update the maxLCM if this is // greater than its existing value maxLCM = max(maxLCM, (arr[i] * arr[j]) / __gcd(arr[i], arr[j])); } } // Return the highest value of LCM return maxLCM; } // Driver code int main() { int arr[] = { 17, 3, 8, 6 }; int n = sizeof (arr) / sizeof (arr[0]); cout << maxLcmOfPairs(arr, n); return 0; } |
Java
// Java implementation to find the maximum // LCM of pairs in an array import java.util.*; class GFG { // Function comparing all LCM pairs static int maxLcmOfPairs( int arr[], int n) { // To store the highest LCM int maxLCM = - 1 ; // To generate all pairs from array for ( int i = 0 ; i < n; i++) { for ( int j = i + 1 ; j < n; j++) { // Find LCM of the pair // Update the maxLCM if this is // greater than its existing value maxLCM = Math.max( maxLCM, (arr[i] * arr[j]) / __gcd(arr[i], arr[j])); } } // Return the highest value of LCM return maxLCM; } static int __gcd( int a, int b) { return b == 0 ? a : __gcd(b, a % b); } // Driver code public static void main(String[] args) { int arr[] = { 17 , 3 , 8 , 6 }; int n = arr.length; System.out.print(maxLcmOfPairs(arr, n)); } } // This code is contributed by sapnasingh4991 |
Python3
# Python3 implementation to find the # maximum LCM of pairs in an array from math import gcd # Function comparing all LCM pairs def maxLcmOfPairs(arr, n): # To store the highest LCM maxLCM = - 1 # To generate all pairs from array for i in range (n): for j in range (i + 1 , n, 1 ): # Find LCM of the pair # Update the maxLCM if this is # greater than its existing value maxLCM = max (maxLCM, (arr[i] * arr[j]) / / gcd(arr[i], arr[j])) # Return the highest value of LCM return maxLCM # Driver code if __name__ = = '__main__' : arr = [ 17 , 3 , 8 , 6 ] n = len (arr) print (maxLcmOfPairs(arr, n)) # This code is contributed by hupendraSingh |
C#
// C# implementation to find the maximum // LCM of pairs in an array using System; class GFG { // Function comparing all LCM pairs static int maxLcmOfPairs( int [] arr, int n) { // To store the highest LCM int maxLCM = -1; // To generate all pairs from array for ( int i = 0; i < n; i++) { for ( int j = i + 1; j < n; j++) { // Find LCM of the pair // Update the maxLCM if this is // greater than its existing value maxLCM = Math.Max( maxLCM, (arr[i] * arr[j]) / __gcd(arr[i], arr[j])); } } // Return the highest value of LCM return maxLCM; } static int __gcd( int a, int b) { return b == 0 ? a : __gcd(b, a % b); } // Driver code public static void Main() { int [] arr = { 17, 3, 8, 6 }; int n = arr.Length; Console.Write(maxLcmOfPairs(arr, n)); } } // This code is contributed by Code_Mech |
Javascript
<script> // javascript implementation to find the maximum // LCM of pairs in an array // Function comparing all LCM pairs function maxLcmOfPairs(arr , n) { // To store the highest LCM var maxLCM = -1; // To generate all pairs from array for (i = 0; i < n; i++) { for (j = i + 1; j < n; j++) { // Find LCM of the pair // Update the maxLCM if this is // greater than its existing value maxLCM = Math.max(maxLCM, (arr[i] * arr[j]) / __gcd(arr[i], arr[j])); } } // Return the highest value of LCM return maxLCM; } function __gcd(a , b) { return b == 0 ? a : __gcd(b, a % b); } // Driver code var arr = [ 17, 3, 8, 6 ]; var n = arr.length; document.write(maxLcmOfPairs(arr, n)); // This code is contributed by umadevi9616 </script> |
136
Another Approach:
We can use Greedy Method. For applying the greedy approach we have to sort the given array and then comparing LCM of pairs of elements of the array and finally compute the maximum value of LCM.
Below is the implementation of the above approach:
C++
// C++ implementation to find the maximum // LCM of pairs in an array #include <bits/stdc++.h> using namespace std; // Function for the highest value of LCM pairs int greedyLCM( int arr[], int n) { // Sort the given array sort(arr, arr + n); // Compute the highest LCM int maxLCM = arr[n - 1]; for ( int i = n - 1; i >= 0; i--) { if (arr[i] * arr[i] < maxLCM) break ; for ( int j = i - 1; j >= 0; j--) { if (arr[i] * arr[j] < maxLCM) break ; else // Find LCM of the pair // Update the maxLCM if this is // greater than its existing value maxLCM = max(maxLCM, (arr[i] * arr[j]) / __gcd(arr[i], arr[j])); } } // return the maximum lcm return maxLCM; } // Driver code int main() { int arr[] = { 17, 3, 8, 6 }; int n = sizeof (arr) / sizeof (arr[0]); cout << greedyLCM(arr, n); return 0; } |
Java
// Java implementation to find the // maximum LCM of pairs in an array import java.util.*; class GFG { // Function for the highest value // of LCM pairs static int greedyLCM( int arr[], int n) { // Sort the given array Arrays.sort(arr); // Compute the highest LCM int maxLCM = arr[n - 1 ]; for ( int i = n - 1 ; i >= 0 ; i--) { if (arr[i] * arr[i] < maxLCM) break ; for ( int j = i - 1 ; j >= 0 ; j--) { if (arr[i] * arr[j] < maxLCM) break ; else // Find LCM of the pair // Update the maxLCM if this is // greater than its existing value maxLCM = Math.max( maxLCM, (arr[i] * arr[j]) / __gcd(arr[i], arr[j])); } } // Return the maximum lcm return maxLCM; } static int __gcd( int a, int b) { return b == 0 ? a : __gcd(b, a % b); } // Driver code public static void main(String[] args) { int arr[] = { 17 , 3 , 8 , 6 }; int n = arr.length; System.out.print(greedyLCM(arr, n)); } } // This code is contributed by Amit Katiyar |
Python3
# Python3 implementation to # find the maximum LCM of # pairs in an array from math import gcd # Function for the highest # value of LCM pairs def greedyLCM(arr, n): # Sort the given array arr.sort() # Compute the highest LCM maxLCM = arr[n - 1 ] for i in range (n - 1 , - 1 , - 1 ): if (arr[i] * arr[i] < maxLCM): break for j in range (i - 1 , - 1 , - 1 ): if (arr[i] * arr[j] < maxLCM): break else : # Find LCM of the pair # Update the maxLCM if this is # greater than its existing value maxLCM = max (maxLCM, (arr[i] * arr[j]) / / gcd(arr[i], arr[j])) # Return the maximum lcm return maxLCM # Driver code arr = [ 17 , 3 , 8 , 6 ] n = len (arr) print (greedyLCM(arr, n)) # This code is contributed by divyeshrabadiya07 |
C#
// C# implementation to find the // maximum LCM of pairs in an array using System; class GFG { // Function for the highest value // of LCM pairs static int greedyLCM( int [] arr, int n) { // Sort the given array Array.Sort(arr); // Compute the highest LCM int maxLCM = arr[n - 1]; for ( int i = n - 1; i >= 0; i--) { if (arr[i] * arr[i] < maxLCM) break ; for ( int j = i - 1; j >= 0; j--) { if (arr[i] * arr[j] < maxLCM) break ; else // Find LCM of the pair // Update the maxLCM if this is // greater than its existing value maxLCM = Math.Max( maxLCM, (arr[i] * arr[j]) / __gcd(arr[i], arr[j])); } } // Return the maximum lcm return maxLCM; } static int __gcd( int a, int b) { return b == 0 ? a : __gcd(b, a % b); } // Driver code public static void Main(String[] args) { int [] arr = { 17, 3, 8, 6 }; int n = arr.Length; Console.Write(greedyLCM(arr, n)); } } // This code is contributed by Amit Katiyar |
Javascript
<script> // Javascript implementation to find the // maximum LCM of pairs in an array // Function for the highest value // of LCM pairs function greedyLCM(arr, n) { // Sort the given array arr.sort( function (a, b){ return a - b}); // Compute the highest LCM let maxLCM = arr[n - 1]; for (let i = n - 1; i >= 0; i--) { if (arr[i] * arr[i] < maxLCM) break ; for (let j = i - 1; j >= 0; j--) { if (arr[i] * arr[j] < maxLCM) break ; else // Find LCM of the pair // Update the maxLCM if this is // greater than its existing value maxLCM = Math.max(maxLCM, parseInt((arr[i] * arr[j]) / __gcd(arr[i], arr[j]), 10)); } } // Return the maximum lcm return maxLCM; } function __gcd(a, b) { return b == 0 ? a : __gcd(b, a % b); } // Driver code let arr = [ 17, 3, 8, 6 ]; let n = arr.length; document.write(greedyLCM(arr, n)); // This code is contributed by mukesh07 </script> |
136
Time Complexity: O(N2)