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