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: #include <bits/stdc++.h> NEW_LINE using namespace std ; void parity ( vector < int > even , vector < int > odd , vector < int > v , int i , int & min ) { if ( i == v . size ( ) || even . size ( ) == 0 && odd . size ( ) == 0 ) { int count = 0 ; for ( int j = 0 ; j < v . size ( ) - 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 , min ) ; else { if ( even . size ( ) != 0 ) { int x = even . back ( ) ; even . pop_back ( ) ; v [ i ] = x ; parity ( even , odd , v , i + 1 , min ) ; even . push_back ( x ) ; } if ( odd . size ( ) != 0 ) { int x = odd . back ( ) ; odd . pop_back ( ) ; v [ i ] = x ; parity ( even , odd , v , i + 1 , min ) ; odd . push_back ( x ) ; } } } void minDiffParity ( vector < int > v , int n ) { vector < int > even ; vector < int > odd ; unordered_map < int , int > m ; for ( int i = 1 ; i <= n ; i ++ ) m [ i ] = 1 ; for ( int i = 0 ; i < v . size ( ) ; i ++ ) { if ( v [ i ] != -1 ) m . erase ( v [ i ] ) ; } for ( auto i : m ) { if ( i . first % 2 == 0 ) even . push_back ( i . first ) ; else odd . push_back ( i . first ) ; } int min = 1000 ; parity ( even , odd , v , 0 , min ) ; cout << min << endl ; } int main ( ) { int n = 8 ; vector < int > v = { 2 , 1 , 4 , -1 , -1 , 6 , -1 , 8 } ; minDiffParity ( v , n ) ; return 0 ; }