Minimize the count of adjacent pairs with different parity | Java 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
import java . util . * ; public class Main { static int min ; static void parity ( List < Integer > even , List < Integer > odd , List < Integer > v , int i ) { if ( i == v . size ( ) || even . size ( ) == 0 && odd . size ( ) == 0 ) { int count = 0 ; for ( int j = 0 ; j < v . size ( ) - 1 ; j ++ ) { if ( v . get ( j ) % 2 != v . get ( j + 1 ) % 2 ) count ++ ; } if ( count < min ) min = count ; return ; } if ( v . get ( i ) != - 1 ) parity ( even , odd , v , i + 1 ) ; else { if ( even . size ( ) != 0 ) { int x = even . get ( even . size ( ) - 1 ) ; even . remove ( even . size ( ) - 1 ) ; v . set ( i , x ) ; parity ( even , odd , v , i + 1 ) ; even . add ( x ) ; } if ( odd . size ( ) != 0 ) { int x = odd . get ( odd . size ( ) - 1 ) ; odd . remove ( odd . size ( ) - 1 ) ; v . set ( i , x ) ; parity ( even , odd , v , i + 1 ) ; odd . add ( x ) ; } } } static void minDiffParity ( List < Integer > v , int n ) { List < Integer > even = new ArrayList < Integer > ( ) ; List < Integer > odd = new ArrayList < Integer > ( ) ; HashMap < Integer , Integer > m = new HashMap < > ( ) ; for ( int i = 1 ; i <= n ; i ++ ) { if ( m . containsKey ( i ) ) { m . replace ( i , 1 ) ; } else { m . put ( i , 1 ) ; } } for ( int i = 0 ; i < v . size ( ) ; i ++ ) { if ( v . get ( i ) != - 1 ) m . remove ( v . get ( i ) ) ; } for ( Map . Entry < Integer , Integer > i : m . entrySet ( ) ) { if ( i . getKey ( ) % 2 == 0 ) { even . add ( i . getKey ( ) ) ; } else { odd . add ( i . getKey ( ) ) ; } } min = 1000 ; parity ( even , odd , v , 0 ) ; System . out . println ( min ) ; } public static void main ( String [ ] args ) { int n = 8 ; List < Integer > v = new ArrayList < Integer > ( ) ; 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 ) ; } }