Count of replacements required to make the sum of all Pairs of given type from the Array equal | C ++ Program to 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
#include <bits/stdc++.h> NEW_LINE #define int  long long int NEW_LINE using namespace std ; const int inf = 1e18 ; int minimumReplacement ( int * arr , int N , int K ) { int ans = inf ; vector < int > max_values ; vector < int > min_values ; map < int , int > sum_equal_to_x ; for ( int i = 0 ; i < N / 2 ; i ++ ) { int mn = min ( arr [ i ] , arr [ N - i - 1 ] ) ; int mx = max ( arr [ i ] , arr [ N - i - 1 ] ) ; sum_equal_to_x [ arr [ i ] + arr [ N - i - 1 ] ] ++ ; min_values . push_back ( mn ) ; max_values . push_back ( mx ) ; } sort ( max_values . begin ( ) , max_values . end ( ) ) ; sort ( min_values . begin ( ) , min_values . end ( ) ) ; for ( int x = 2 ; x <= 2 * K ; x ++ ) { int mp1 = lower_bound ( max_values . begin ( ) , max_values . end ( ) , x - K ) - max_values . begin ( ) ; int mp2 = lower_bound ( min_values . begin ( ) , min_values . end ( ) , x ) - min_values . begin ( ) ; int rep2 = mp1 + ( N / 2 - mp2 ) ; int rep0 = sum_equal_to_x [ x ] ; int rep1 = ( N / 2 - rep2 - rep0 ) ; ans = min ( ans , rep2 * 2 + rep1 ) ; } return ans ; } int32_t main ( ) { int N = 4 ; int K = 3 ; int arr [ ] = { 1 , 2 , 2 , 1 } ; cout << minimumReplacement ( arr , N , K ) ; return 0 ; }