text: Minimize the count of adjacent pairs with different parity | Python3 implementation of above approach ; Recursive function to calculate minimum adjacent pairs with different parity ; If all the numbers are placed ; If replacement is not required ; If replacement is required ; backtracking ; backtracking ; Function to display the minimum number of adjacent elements with different parity ; Store no of even numbers not present in the array ; Store no of odd numbers not present in the array ; Erase exisiting numbers ; Store non - exisiting even and odd numbers ; Driver code
code: mn = 1000 NEW_LINE def parity ( even , odd , v , i ) : NEW_LINE INDENT global mn NEW_LINE if ( i == len ( v ) or len ( even ) == 0 or len ( odd ) == 0 ) : NEW_LINE INDENT count = 0 NEW_LINE for j in range ( len ( v ) - 1 ) : NEW_LINE INDENT if ( v [ j ] % 2 != v [ j + 1 ] % 2 ) : NEW_LINE INDENT count += 1 NEW_LINE DEDENT DEDENT if ( count < mn ) : NEW_LINE INDENT mn = count NEW_LINE DEDENT return NEW_LINE DEDENT if ( v [ i ] != - 1 ) : NEW_LINE INDENT parity ( even , odd , v , i + 1 ) NEW_LINE DEDENT else : NEW_LINE INDENT if ( len ( even ) != 0 ) : NEW_LINE INDENT x = even [ len ( even ) - 1 ] NEW_LINE even . remove ( even [ len ( even ) - 1 ] ) NEW_LINE v [ i ] = x NEW_LINE parity ( even , odd , v , i + 1 ) NEW_LINE even . append ( x ) NEW_LINE DEDENT if ( len ( odd ) != 0 ) : NEW_LINE INDENT x = odd [ len ( odd ) - 1 ] NEW_LINE odd . remove ( odd [ len ( odd ) - 1 ] ) NEW_LINE v [ i ] = x NEW_LINE parity ( even , odd , v , i + 1 ) NEW_LINE odd . append ( x ) NEW_LINE DEDENT DEDENT DEDENT def mnDiffParity ( v , n ) : NEW_LINE INDENT global mn NEW_LINE even = [ ] NEW_LINE odd = [ ] NEW_LINE m = { i : 0 for i in range ( 100 ) } NEW_LINE for i in range ( 1 , n + 1 ) : NEW_LINE INDENT m [ i ] = 1 NEW_LINE DEDENT for i in range ( len ( v ) ) : NEW_LINE INDENT if ( v [ i ] != - 1 ) : NEW_LINE INDENT m . pop ( v [ i ] ) NEW_LINE DEDENT DEDENT for key in m . keys ( ) : NEW_LINE INDENT if ( key % 2 == 0 ) : NEW_LINE INDENT even . append ( key ) NEW_LINE DEDENT else : NEW_LINE INDENT odd . append ( key ) NEW_LINE DEDENT DEDENT parity ( even , odd , v , 0 ) NEW_LINE print ( mn + 4 ) NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT n = 8 NEW_LINE v = [ 2 , 1 , 4 , - 1 , - 1 , 6 , - 1 , 8 ] NEW_LINE mnDiffParity ( v , n ) NEW_LINE DEDENT