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
function GCD ( a , b ) { if ( b == 0 ) return a ; return GCD ( b , a % b ) ; } function findPartition ( nums , N ) { var prefix = Array ( N ) , suffix = Array ( N ) , i , k ; prefix [ 0 ] = nums [ 0 ] ; for ( i = 1 ; i < N ; i ++ ) { prefix [ i ] = prefix [ i - 1 ] * nums [ i ] ; } suffix [ N - 1 ] = nums [ N - 1 ] ; for ( i = N - 2 ; i >= 0 ; i -- ) { suffix [ i ] = suffix [ i + 1 ] * nums [ i ] ; } for ( k = 0 ; k < N - 1 ; k ++ ) { if ( GCD ( prefix [ k ] , suffix [ k + 1 ] ) == 1 ) { return k ; } } return - 1 ; } var arr = [ 2 , 3 , 4 , 5 ] ; var N = arr . length ; document . write ( findPartition ( arr , N ) ) ;