text: Minimize the count of adjacent pairs with different parity | C # 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: using System ; using System . Collections . Generic ; class GFG { static int min ; static void parity ( List < int > even , List < int > odd , List < int > v , int i ) { if ( i == v . Count even . Count == 0 && odd . Count == 0 ) { int count = 0 ; for ( int j = 0 ; j < v . Count - 1 ; j ++ ) { if ( v [ j ] % 2 != v [ j + 1 ] % 2 ) count ++ ; } if ( count < min ) min = count ; return ; } if ( v [ i ] != - 1 ) parity ( even , odd , v , i + 1 ) ; else { if ( even . Count != 0 ) { int x = even [ even . Count - 1 ] ; even . RemoveAt ( even . Count - 1 ) ; v [ i ] = x ; parity ( even , odd , v , i + 1 ) ; even . Add ( x ) ; } if ( odd . Count != 0 ) { int x = odd [ odd . Count - 1 ] ; odd . RemoveAt ( odd . Count - 1 ) ; v [ i ] = x ; parity ( even , odd , v , i + 1 ) ; odd . Add ( x ) ; } } } static void minDiffParity ( List < int > v , int n ) { List < int > even = new List < int > ( ) ; List < int > odd = new List < int > ( ) ; Dictionary < int , int > m = new Dictionary < int , int > ( ) ; for ( int i = 1 ; i <= n ; i ++ ) { if ( m . ContainsKey ( i ) ) { m [ i ] = 1 ; } else { m . Add ( i , 1 ) ; } } for ( int i = 0 ; i < v . Count ; i ++ ) { if ( v [ i ] != - 1 ) m . Remove ( v [ i ] ) ; } foreach ( KeyValuePair < int , int > i in m ) { if ( i . Key % 2 == 0 ) { even . Add ( i . Key ) ; } else { odd . Add ( i . Key ) ; } } min = 1000 ; parity ( even , odd , v , 0 ) ; Console . WriteLine ( min ) ; } static void Main ( ) { int n = 8 ; List < int > v = new List < int > ( ) ; v . Add ( 2 ) ; v . Add ( 1 ) ; v . Add ( 4 ) ; v . Add ( - 1 ) ; v . Add ( - 1 ) ; v . Add ( 6 ) ; v . Add ( - 1 ) ; v . Add ( 8 ) ; minDiffParity ( v , n ) ; } }