Count of replacements required to make the sum of all Pairs of given type from the Array equal | Java program implement the above approach ; Function to find the minimum replacements required ; Stores the maximum and minimum values for every pair of the form arr [ i ] , arr [ n - i - 1 ] ; Map for storing frequencies of every sum formed by pairs ; Minimum element in the pair ; Maximum element in the pair ; Incrementing the frequency of sum encountered ; Insert minimum and maximum values ; Sorting the vectors ; Iterate over all possible values of x ; Count of pairs for which x > x + k ; Count of pairs for which x < mn + 1 ; Count of pairs requiring 2 replacements ; Count of pairs requiring no replacements ; Count of pairs requiring 1 replacement ; Update the answer ; Return the answer ; Driver Code
import java . util . * ; import java . io . * ; class GFG { static int inf = ( int ) 1e18 ; static int minimumReplacement ( int [ ] arr , int N , int K ) { int ans = inf ; ArrayList < Integer > max_values = new ArrayList < > ( ) ; ArrayList < Integer > min_values = new ArrayList < > ( ) ; Map < Integer , Integer > sum_equal_to_x = new HashMap < > ( ) ; for ( int i = 0 ; i < N / 2 ; i ++ ) { int mn = Math . min ( arr [ i ] , arr [ N - i - 1 ] ) ; int mx = Math . max ( arr [ i ] , arr [ N - i - 1 ] ) ; sum_equal_to_x . put ( arr [ i ] + arr [ N - i - 1 ] , sum_equal_to_x . getOrDefault ( arr [ i ] + arr [ N - i - 1 ] , 0 ) + 1 ) ; min_values . add ( mn ) ; max_values . add ( mx ) ; } Collections . sort ( max_values ) ; Collections . sort ( min_values ) ; for ( int x = 2 ; x <= 2 * K ; x ++ ) { int mp1 = max_values . indexOf ( x - K ) ; int mp2 = min_values . indexOf ( x ) ; int rep2 = mp1 + ( N / 2 - mp2 ) ; int rep0 = sum_equal_to_x . getOrDefault ( x , - 1 ) ; int rep1 = ( N / 2 - rep2 - rep0 ) ; ans = Math . min ( ans , rep2 * 2 + rep1 ) ; } return ans ; } public static void main ( String [ ] args ) { int N = 4 ; int K = 3 ; int arr [ ] = { 1 , 2 , 2 , 1 } ; System . out . print ( minimumReplacement ( arr , N , K ) ) ; } }