Minimum index to split array into subarrays with co | Function to find the GCD of 2 numbers ; Base Case ; Find the GCD recursively ; Function to find the minimum partition index K s . t . product of both subarrays around that partition are co - prime ; Stores the prefix and suffix array product ; Update the prefix array ; Update the suffix array ; Iterate the given array ; Check if prefix [ k ] and suffix [ k + 1 ] are co - prime ; If no index for partition exists , then return - 1 ; Driver Code ; Function call
def GCD ( a , b ) : NEW_LINE INDENT if ( b == 0 ) : NEW_LINE INDENT return a NEW_LINE DEDENT return GCD ( b , a % b ) NEW_LINE DEDENT def findPartition ( nums , N ) : NEW_LINE INDENT prefix = [ 0 ] * N NEW_LINE suffix = [ 0 ] * N NEW_LINE prefix [ 0 ] = nums [ 0 ] NEW_LINE for i in range ( 1 , N ) : NEW_LINE INDENT prefix [ i ] = ( prefix [ i - 1 ] * nums [ i ] ) NEW_LINE DEDENT suffix [ N - 1 ] = nums [ N - 1 ] NEW_LINE for i in range ( N - 2 , - 1 , - 1 ) : NEW_LINE INDENT suffix [ i ] = ( suffix [ i + 1 ] * nums [ i ] ) NEW_LINE DEDENT for k in range ( N - 1 ) : NEW_LINE INDENT if ( GCD ( prefix [ k ] , suffix [ k + 1 ] ) == 1 ) : NEW_LINE INDENT return k NEW_LINE DEDENT DEDENT return - 1 NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT arr = [ 2 , 3 , 4 , 5 ] NEW_LINE N = len ( arr ) NEW_LINE print ( findPartition ( arr , N ) ) NEW_LINE DEDENT