Remove an element to minimize the LCM of the given array | 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
function lcm ( a , b ) { let GCD = __gcd ( a , b ) ; return Math . floor ( ( a * b ) / GCD ) ; } function __gcd ( a , b ) { return b == 0 ? a : __gcd ( b , a % b ) ; } function MinLCM ( a , n ) { let Prefix = new Array ( n + 2 ) ; let Suffix = new Array ( n + 2 ) ; Prefix [ 1 ] = a [ 0 ] ; for ( let i = 2 ; i <= n ; i += 1 ) { Prefix [ i ] = lcm ( Prefix [ i - 1 ] , a [ i - 1 ] ) ; } Suffix [ n ] = a [ n - 1 ] ; for ( let i = n - 1 ; i >= 1 ; i -= 1 ) { Suffix [ i ] = lcm ( Suffix [ i + 1 ] , a [ i - 1 ] ) ; } let ans = Math . min ( Suffix [ 2 ] , Prefix [ n - 1 ] ) ; for ( let i = 2 ; i < n ; i += 1 ) { ans = Math . min ( ans , lcm ( Prefix [ i - 1 ] , Suffix [ i + 1 ] ) ) ; } return ans ; } let a = [ 5 , 15 , 9 , 36 ] ; let n = a . length ; document . write ( MinLCM ( a , n ) ) ;