Minimum LCM of all pairs in a given array | Python3 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
import sys NEW_LINE def minLCM ( arr , n ) : NEW_LINE INDENT mx = 0 NEW_LINE for i in range ( n ) : NEW_LINE INDENT mx = max ( mx , arr [ i ] ) NEW_LINE DEDENT mul = [ [ ] for i in range ( mx + 1 ) ] NEW_LINE for i in range ( n ) : NEW_LINE INDENT if ( len ( mul [ arr [ i ] ] ) > 1 ) : NEW_LINE INDENT continue NEW_LINE DEDENT mul [ arr [ i ] ] . append ( arr [ i ] ) NEW_LINE DEDENT for i in range ( 1 , mx + 1 ) : NEW_LINE INDENT for j in range ( i + i , mx + 1 , i ) : NEW_LINE INDENT if ( len ( mul [ i ] ) > 1 ) : NEW_LINE INDENT break NEW_LINE DEDENT for k in mul [ j ] : NEW_LINE INDENT if ( len ( mul [ i ] ) > 1 ) : NEW_LINE INDENT break NEW_LINE DEDENT mul [ i ] . append ( k ) NEW_LINE DEDENT DEDENT DEDENT ans = sys . maxsize NEW_LINE for i in range ( 1 , mx + 1 ) : NEW_LINE INDENT if ( len ( mul [ i ] ) <= 1 ) : NEW_LINE INDENT continue NEW_LINE DEDENT a , b = mul [ i ] [ 0 ] , mul [ i ] [ 1 ] NEW_LINE lcm = ( a * b ) // i NEW_LINE ans = min ( ans , lcm ) NEW_LINE DEDENT return ans NEW_LINE DEDENT arr = [ 2 , 4 , 3 , 6 , 5 ] NEW_LINE n = len ( arr ) NEW_LINE print ( minLCM ( arr , n ) ) NEW_LINE