Given an integer array arr of length N and an integer K, the task is to find the number of array elements to be replaced by a value from the range [1, K] such that each pair (arr[i], arr[N – 1 – i] have equal sum.
Examples :
Input: arr[] = {1, 2, 2, 1}, K = 3
Output: 1
Explanation:
Replace arr[0] with 3, so that the array becomes {3, 2, 2, 1}.
Now, it can be seen that arr[0] + arr[3] = arr[1] + arr[2] = 4.Input: arr[] = {1, 2, 1, 2, 1, 2}
Output: 0
Explanation:
No need to make any changes as arr[0] + arr[5] = arr[1] + arr[4] = arr[2] + arr[3] = 3
Naive Approach :
The simplest approach to this problem could be like iterate for all possible values of X, which can be any number in the range 1 to 2*K, and find the number of operation require to achieve pair sum equal to X. And finally return the minimum numbers of replacement from all operations.
Time Complexity : O (N * K)
Auxiliary Space : O (1)
Efficient Approach: The above approach can be optimized by the following observations:
- X can clearly take values in the range [2, 2 * K].
- Considering pairs arr[i] and arr[N – i – 1], it can be observed that the sum of any pair can be made equal to X in 0, 1 or 2 replacements.
- Let the maximum of these two numbers be mx and minimum be mn. In one replacement, the sum of this pair will be in the range [mn + 1, mx + K].
- The pair for which mx is less than ( X – K) and mn is greater than or equal to X will need 2 replacements.
- Simply insert mx and mn for all pairs in two different vectors, sort them and apply binary search to find the number of pairs for which 2 replacements are required.
- Find the pairs which do not need any replacement by using Map by storing the frequencies of each sum.
- Finally number of pairs which require one replacement can be calculated by the equation (N / 2 – (pairs which need 2 replacements + pairs which need no replacement) ).
Follow these steps to find the solve the problem:
- Find maximum and minimum for all pairs arr [ i ], arr [ N – i – 1 ] and store them in max_values and min_values vectors respectively. Also store the frequencies of sum of all such pairs in a map.
- Sort the vectors max_values and min_values.
- Iterate from X = 2 to X = 2 * K, and for every value of X find the total number of replacements as described in the approach above. Update the answer as:
answer = min ( answer, 2 * (number of pairs for which we need to make 2 replacements) + (number of pairs for which we need to make one replacement) ).
Illustration :
arr[] = { 1, 2, 2, 1 }, K = 3
max_values = {1, 2}
min_values = {1, 2}
map = {{2, 1}, {4, 1}}
At X = 4, minimum replacement is required, that is, only 1 replacement, either conversion arr[0] to 3 or arr[3] to 3, is required to make the sum of all pairs equal to 4.
Below is the implementation of the above approach:
C++
// C++ Program to implement the // above approach #include <bits/stdc++.h> #define int long long int using namespace std; const int inf = 1e18; // Function to find the minimum // replacements required int minimumReplacement(int* arr, int N, int K) { int ans = inf; // Stores the maximum and minimum // values for every pair of // the form arr[i], arr[n-i-1] vector<int> max_values; vector<int> min_values; // Map for storing frequencies // of every sum formed by pairs map<int, int> sum_equal_to_x; for (int i = 0; i < N / 2; i++) { // Minimum element in the pair int mn = min(arr[i], arr[N - i - 1]); // Maximum element in the pair int mx = max(arr[i], arr[N - i - 1]); // Incrementing the frequency of // sum encountered sum_equal_to_x[arr[i] + arr[N - i - 1]]++; // Insert minimum and maximum values min_values.push_back(mn); max_values.push_back(mx); } // Sorting the vectors sort(max_values.begin(), max_values.end()); sort(min_values.begin(), min_values.end()); // Iterate over all possible values of x for (int x = 2; x <= 2 * K; x++) { // Count of pairs for which x > x + k int mp1 = lower_bound(max_values.begin(), max_values.end(), x - K) - max_values.begin(); // Count of pairs for which x < mn + 1 int mp2 = lower_bound(min_values.begin(), min_values.end(), x) - min_values.begin(); // Count of pairs requiring 2 replacements int rep2 = mp1 + (N / 2 - mp2); // Count of pairs requiring no replacements int rep0 = sum_equal_to_x[x]; // Count of pairs requiring 1 replacement int rep1 = (N / 2 - rep2 - rep0); // Update the answer ans = min(ans, rep2 * 2 + rep1); } // Return the answer return ans; } // Driver Code int32_t main() { int N = 4; int K = 3; int arr[] = { 1, 2, 2, 1 }; cout << minimumReplacement(arr, N, K); return 0; } |
Java
// Java program implement // the above approach import java.util.*; import java.io.*; class GFG{ static int inf = (int)1e18; // Function to find the minimum // replacements required static int minimumReplacement(int[] arr, int N, int K) { int ans = inf; // Stores the maximum and minimum // values for every pair of // the form arr[i], arr[n-i-1] ArrayList<Integer> max_values = new ArrayList<>(); ArrayList<Integer> min_values = new ArrayList<>(); // Map for storing frequencies // of every sum formed by pairs Map<Integer, Integer> sum_equal_to_x = new HashMap<>(); for(int i = 0; i < N / 2; i++) { // Minimum element in the pair int mn = Math.min(arr[i], arr[N - i - 1]); // Maximum element in the pair int mx = Math.max(arr[i], arr[N - i - 1]); // Incrementing the frequency of // sum encountered sum_equal_to_x.put(arr[i] + arr[N - i - 1], sum_equal_to_x.getOrDefault(arr[i] + arr[N - i - 1], 0) + 1); // Insert minimum and maximum values min_values.add(mn); max_values.add(mx); } // Sorting the vectors Collections.sort(max_values); Collections.sort(min_values); // Iterate over all possible values of x for(int x = 2; x <= 2 * K; x++) { // Count of pairs for which x > x + k int mp1 = max_values.indexOf(x - K); // Count of pairs for which x < mn + 1 int mp2 = min_values.indexOf(x); // Count of pairs requiring 2 replacements int rep2 = mp1 + (N / 2 - mp2); // Count of pairs requiring no replacements int rep0 = sum_equal_to_x.getOrDefault(x, -1); // Count of pairs requiring 1 replacement int rep1 = (N / 2 - rep2 - rep0); // Update the answer ans = Math.min(ans, rep2 * 2 + rep1); } // Return the answer return ans; } // Driver Code 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)); } } // This code is contributed by offbeat |
Python3
# Python3 program to implement the # above approach inf = 10**18def firstOccurrence(numbers, length, searchnum): answer = -1 start = 0 end = length - 1 while start <= end: middle = (start + end) // 2 if numbers[middle] == searchnum: answer = middle end = middle - 1 elif numbers[middle] > searchnum: end = middle - 1 else: start = middle + 1 return answer # Function to find the minimum # replacements required def minimumReplacement(arr, N, K): ans = inf # Stores the maximum and minimum # values for every pair of # the form arr[i], arr[n-i-1] max_values = [] min_values = [] # Map for storing frequencies # of every sum formed by pairs sum_equal_to_x = dict() for i in range(N // 2): # Minimum element in the pair mn = min(arr[i], arr[N - i - 1]) # Maximum element in the pair mx = max(arr[i], arr[N - i - 1]) # Incrementing the frequency of # sum encountered if(arr[i] + arr[N - i - 1] not in sum_equal_to_x): sum_equal_to_x[arr[i] + arr[N - i - 1]] = 0 sum_equal_to_x[arr[i] + arr[N - i - 1]] += 1 # Insert minimum and maximum values min_values.append(mn) max_values.append(mx) max_values.sort() min_values.sort() # Iterate over all possible values of x for x in range(2, 2 * K + 1): # Count of pairs for which x > x + k mp1 = firstOccurrence( max_values, len(max_values), x - K) # Count of pairs for which x < mn + 1 mp2 = firstOccurrence( min_values, len(min_values), x) # Count of pairs requiring 2 replacements rep2 = mp1 + (N // 2 - mp2) # Count of pairs requiring no replacements if x in sum_equal_to_x: rep0 = sum_equal_to_x[x] else: rep0 = 0 # Count of pairs requiring 1 replacement rep1 = (N // 2 - rep2 - rep0) # Update the answer ans = min(ans, rep2 * 2 + rep1) # Return the answer return ans# Driver Code if __name__=='__main__': N = 4 K = 3 arr = [ 1, 2, 2, 1 ] print(minimumReplacement(arr, N, K)) # This code is contributed by pratham76 |
C#
// C# program implement// the above approachusing System;using System.Collections; using System.Collections.Generic; class GFG{// Function to find the minimum// replacements requiredstatic int minimumReplacement(int[] arr, int N, int K){ int ans = int.MaxValue; // Stores the maximum and minimum // values for every pair of // the form arr[i], arr[n-i-1] ArrayList max_values = new ArrayList(); ArrayList min_values = new ArrayList(); // Map for storing frequencies // of every sum formed by pairs Dictionary<int, int> sum_equal_to_x = new Dictionary<int, int>(); for(int i = 0; i < N / 2; i++) { // Minimum element in the pair int mn = Math.Min(arr[i], arr[N - i - 1]); // Maximum element in the pair int mx = Math.Max(arr[i], arr[N - i - 1]); // Incrementing the frequency of // sum encountered sum_equal_to_x[arr[i] + arr[N - i - 1]] = sum_equal_to_x.GetValueOrDefault(arr[i] + arr[N - i - 1], 0) + 1; // Insert minimum and maximum values min_values.Add(mn); max_values.Add(mx); } // Sorting the vectors max_values.Sort(); min_values.Sort(); // Iterate over all possible values of x for(int x = 2; x <= 2 * K; x++) { // Count of pairs for which x > x + k int mp1 = max_values.IndexOf(x - K); // Count of pairs for which x < mn + 1 int mp2 = min_values.IndexOf(x); // Count of pairs requiring 2 replacements int rep2 = mp1 + (N / 2 - mp2); // Count of pairs requiring no replacements int rep0 = sum_equal_to_x.GetValueOrDefault( x, -1); // Count of pairs requiring 1 replacement int rep1 = (N / 2 - rep2 - rep0); // Update the answer ans = Math.Min(ans, rep2 * 2 + rep1); } // Return the answer return ans;}// Driver Codepublic static void Main(string[] args){ int N = 4; int K = 3; int []arr = { 1, 2, 2, 1 }; Console.Write(minimumReplacement(arr, N, K));}}// This code is contributed by rutvik_56 |
Javascript
<script>// JavaScript program to implement the// above approachconst inf = 10**18function firstOccurrence(numbers, length, searchnum){ let answer = -1 let start = 0 let end = length - 1 while(start <= end){ let middle = Math.floor((start + end)/2) if(numbers[middle] == searchnum){ answer = middle end = middle - 1 } else if(numbers[middle] > searchnum) end = middle - 1 else start = middle + 1 } return answer}// Function to find the minimum// replacements requiredfunction minimumReplacement(arr, N, K){ let ans = inf // Stores the maximum and minimum // values for every pair of // the form arr[i], arr[n-i-1] let max_values = [] let min_values = [] // Map for storing frequencies // of every sum formed by pairs let sum_equal_to_x = new Map() for(let i=0;i<Math.floor(N / 2);i++){ // Minimum element in the pair let mn = Math.min(arr[i], arr[N - i - 1]) // Maximum element in the pair let mx = Math.max(arr[i], arr[N - i - 1]) // Incrementing the frequency of // sum encountered if(sum_equal_to_x.has(arr[i] + arr[N - i - 1])==false) sum_equal_to_x.set(arr[i] + arr[N - i - 1],0) sum_equal_to_x.set(arr[i] + arr[N - i - 1], sum_equal_to_x.get(arr[i] + arr[N - i -1])+1) // Insert minimum and maximum values min_values.push(mn) max_values.push(mx) } max_values.sort() min_values.sort() // Iterate over all possible values of x for(let x=2;x<2 * K + 1;x++){ // Count of pairs for which x > x + k let mp1 = firstOccurrence(max_values, max_values.length, x - K) // Count of pairs for which x < mn + 1 let mp2 = firstOccurrence(min_values, min_values.length, x) // Count of pairs requiring 2 replacements rep2 = mp1 + (Math.floor(N / 2) - mp2) // Count of pairs requiring no replacements if(sum_equal_to_x.has(x)){ rep0 = sum_equal_to_x.get(x) } else rep0 = 0 // Count of pairs requiring 1 replacement rep1 = Math.floor(N /2) - rep2 - rep0 // Update the answer ans = Math.min(ans, rep2 * 2 + rep1) } // Return the answer return ans}// Driver Code let N = 4let K = 3let arr = [ 1, 2, 2, 1 ]document.write(minimumReplacement(arr, N, K)) // This code is contributed by shinjanpatra</script> |
Output
1
Time Complexity: O(NlogN)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
