text: Remove an element to minimize the LCM of the given array | Python3 implementation of the above approach ; Function to return the LCM of two numbers ; Function to return the minimum LCM after removing a single element from the given array ; Prefix and Suffix arrays ; Single state dynamic programming relation for storing LCM of first i elements from the left in Prefix [ i ] ; Initializing Suffix array ; Single state dynamic programming relation for storing LCM of all the elements having index greater than or equal to i in Suffix [ i ] ; If first or last element of the array has to be removed ; If any other element is replaced ; Return the minimum LCM ; Driver code
code: from math import gcd NEW_LINE def lcm ( a , b ) : NEW_LINE INDENT GCD = gcd ( a , b ) ; NEW_LINE return ( a * b ) // GCD ; NEW_LINE DEDENT def MinLCM ( a , n ) : NEW_LINE INDENT Prefix = [ 0 ] * ( n + 2 ) ; NEW_LINE Suffix = [ 0 ] * ( n + 2 ) ; NEW_LINE Prefix [ 1 ] = a [ 0 ] ; NEW_LINE for i in range ( 2 , n + 1 ) : NEW_LINE INDENT Prefix [ i ] = lcm ( Prefix [ i - 1 ] , a [ i - 1 ] ) ; NEW_LINE DEDENT Suffix [ n ] = a [ n - 1 ] ; NEW_LINE for i in range ( n - 1 , 0 , - 1 ) : NEW_LINE INDENT Suffix [ i ] = lcm ( Suffix [ i + 1 ] , a [ i - 1 ] ) ; NEW_LINE DEDENT ans = min ( Suffix [ 2 ] , Prefix [ n - 1 ] ) ; NEW_LINE for i in range ( 2 , n ) : NEW_LINE INDENT ans = min ( ans , lcm ( Prefix [ i - 1 ] , Suffix [ i + 1 ] ) ) ; NEW_LINE DEDENT return ans ; NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT a = [ 5 , 15 , 9 , 36 ] ; NEW_LINE n = len ( a ) ; NEW_LINE print ( MinLCM ( a , n ) ) ; NEW_LINE DEDENT