Count of replacements required to make the sum of all Pairs of given type from the Array equal | Python3 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
inf = 10 ** 18 NEW_LINE def firstOccurance ( numbers , length , searchnum ) : NEW_LINE INDENT answer = - 1 NEW_LINE start = 0 NEW_LINE end = length - 1 NEW_LINE while start <= end : NEW_LINE INDENT middle = ( start + end ) // 2 NEW_LINE if numbers [ middle ] == searchnum : NEW_LINE INDENT answer = middle NEW_LINE end = middle - 1 NEW_LINE DEDENT elif numbers [ middle ] > searchnum : NEW_LINE INDENT end = middle - 1 NEW_LINE DEDENT else : NEW_LINE INDENT start = middle + 1 NEW_LINE DEDENT DEDENT return answer NEW_LINE DEDENT def minimumReplacement ( arr , N , K ) : NEW_LINE INDENT ans = inf NEW_LINE max_values = [ ] NEW_LINE min_values = [ ] NEW_LINE sum_equal_to_x = dict ( ) NEW_LINE for i in range ( N // 2 ) : NEW_LINE INDENT mn = min ( arr [ i ] , arr [ N - i - 1 ] ) NEW_LINE mx = max ( arr [ i ] , arr [ N - i - 1 ] ) NEW_LINE if ( arr [ i ] + arr [ N - i - 1 ] not in sum_equal_to_x ) : NEW_LINE INDENT sum_equal_to_x [ arr [ i ] + arr [ N - i - 1 ] ] = 0 NEW_LINE DEDENT sum_equal_to_x [ arr [ i ] + arr [ N - i - 1 ] ] += 1 NEW_LINE min_values . append ( mn ) NEW_LINE max_values . append ( mx ) NEW_LINE DEDENT max_values . sort ( ) NEW_LINE min_values . sort ( ) NEW_LINE for x in range ( 2 , 2 * K + 1 ) : NEW_LINE INDENT mp1 = firstOccurance ( max_values , len ( max_values ) , x - K ) NEW_LINE mp2 = firstOccurance ( min_values , len ( min_values ) , x ) NEW_LINE rep2 = mp1 + ( N // 2 - mp2 ) NEW_LINE if x in sum_equal_to_x : NEW_LINE INDENT rep0 = sum_equal_to_x [ x ] NEW_LINE DEDENT else : NEW_LINE INDENT rep0 = 0 NEW_LINE DEDENT rep1 = ( N // 2 - rep2 - rep0 ) NEW_LINE ans = min ( ans , rep2 * 2 + rep1 ) NEW_LINE DEDENT return ans NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT N = 4 NEW_LINE K = 3 NEW_LINE arr = [ 1 , 2 , 2 , 1 ] NEW_LINE print ( minimumReplacement ( arr , N , K ) ) NEW_LINE DEDENT