Given an array arr[] of even length N and an integer K, the task is to minimize the count of replacing array elements by an integer from the range [1, K] such that the sum of all pair of equidistant elements from the end of the array is equal.
Examples:
Input: arr[] = {1, 2, 4, 3}, K = 4
Output: 1
Explanation:
Replacing arr[2] by 2 modifies arr[] to {1, 2, 2, 3}.
arr[0] + arr[3] = 1 + 3 = 4.
arr[1] + arr[2] = 2 + 2 = 4.
Therefore, the sum of equidistant elements from the end of the array are equal(i.e., arr[i] + arr[N – 1 – i] = 4 for every i).Input: arr[] = [1, 2, 1, 2], K = 2
Output: 0
Approach: The minimum possible sum of the pair (arr[i], arr[N – i – 1]) is 2 by changing both the values to 1, and the maximum possible sum is 2 * K by changing both the values to K. Hence, for each pair of numbers (at index i and N – 1 – i) l and r:
- By 2 replacements: The sum between the range [2, 2 * K] can be achieved.
- By only 1 replacement:
- The minimum sum that can be achieved, say minSum, is (min(L, R) + 1).
- The maximum sum that can be achieved, say maxSum, is (max(L, R) + K).
- By no replacement: The sum (L + R) remains. Let it be pairSum.
Deducing from the above results, for a pair (L, R):
- In order to get the sum in the range [2, minSum – 1], 2 replacements are required.
- In order to get the sum in the range [minSum, pairSum – 1], 1 replacement is required.
- In order to get the sum pairSum, no replacement is required.
- In order to get the sum in the range [pairSum + 1, maxSum], 1 replacement is required.
- In order to get the sum in the range [maxSum + 1, 2*K], 2 replacements are required.
Therefore, for each pair of array elements
- Start with 2 replacements.
- From minSum onwards, 1 less replacement is required.
- For pairSum, 1 further less replacement is required.
- From pairSum + 1, 1 additional replacement is required.
- From maxSum + 1, 1 further additional replacement is required.
Follow the steps below to solve the problem:
- Initialize an auxiliary array, say memo[], of size (2 * K + 2), where memo[i] denotes the minimum number of replacements required to make the sum of all required pairs equal to i – N.
- Iterate over the indices [0, N/2 – 1] using the variable i.
- Store the left element of the pair, i.e., arr[i] in L, and the right element of the pair, i.e., arr[N – i – 1] in R.
- Decrement memo[min(L, R) + 1] and memo[L + R] by 1.
- Increment memo[L + R+ 1] and memo[max(L, R) + K + 1] by 1.
- Initialize ans as N to store the minimum number of required moves and curr as N to store the prefix sum of the memo[] at each step.
- Find the prefix sum of the array memo[] and in each iteration update the value of curr and ans if curr is less than ans.
- After the above steps, print the value of ans as the result.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to count the minimum replacements // required to make the sum of equidistant // array elements from the end equal void minReplacements(vector<int>& nums, int k) { // Store the size of nums array int N = nums.size(); // Initialize an auxiliary array vector<int> memo(k * 2 + 2, 0); // Iterate nums in range[0, N/2-1] for (int i = 0; i < N / 2; ++i) { // Store the left element and // the right element int l = nums[i], r = nums[N - 1 - i]; // Decrement memo[min(l, r) + 1] by 1 --memo[min(l, r) + 1]; // Decrement memo[l + r] by 1 --memo[l + r]; // Increment memo[l + r + 1] by 1 ++memo[l + r + 1]; // Increment memo[max(l, r) + k + 1] by 1 ++memo[max(l, r) + k + 1]; } // Store the minimum number of moves int ans = N; int curr = N; // Find the prefix sum of memo[] for (int i = 2; i <= k * 2; ++i) { curr += memo[i]; // Update ans ans = min(ans, curr); } // Print the answer cout << ans; } // Driver Code int main() { vector<int> arr{ 1, 2, 4, 3 }; int K = 4; // Function Call minReplacements(arr, K); return 0; } |
Java
// Java program for the above approach import java.util.*; import java.util.Arrays; class GFG{ // Function to count the minimum replacements // required to make the sum of equidistant // array elements from the end equal static void minReplacements(int[] nums, int k) { // Store the size of nums array int N = nums.length; // Initialize an auxiliary array int[] memo = new int[(k * 2 + 2)]; Arrays.fill(memo, 0); // Iterate nums in range[0, N/2-1] for(int i = 0; i < N / 2; ++i) { // Store the left element and // the right element int l = nums[i], r = nums[N - 1 - i]; // Decrement memo[min(l, r) + 1] by 1 --memo[(Math.min(l, r) + 1)]; // Decrement memo[l + r] by 1 --memo[l + r]; // Increment memo[l + r + 1] by 1 ++memo[l + r + 1]; // Increment memo[max(l, r) + k + 1] by 1 ++memo[(Math.max(l, r) + k + 1)]; } // Store the minimum number of moves int ans = N; int curr = N; // Find the prefix sum of memo[] for(int i = 2; i <= k * 2; ++i) { curr += memo[i]; // Update ans ans = Math.min(ans, curr); } // Print the answer System.out.println(ans); } // Driver code public static void main(String[] args) { int[] arr = { 1, 2, 4, 3 }; int K = 4; // Function Call minReplacements(arr, K); } } // This code is contributed by susmitakundugoaldanga |
Python3
# Python3 program for the above approach # Function to count the minimum replacements # required to make the sum of equidistant # array elements from the end equal def minReplacements(nums, k): # Store the size of nums array N = len(nums) # Initialize an auxiliary array memo = [0]*(k * 2 + 2) # Iterate nums in range[0, N/2-1] for i in range(N//2): # Store the left element and # the right element l, r = nums[i], nums[N - 1 - i] # Decrement memo[min(l, r) + 1] by 1 memo[min(l, r) + 1] -= 1 # Decrement memo[l + r] by 1 memo[l + r] -= 1 # Increment memo[l + r + 1] by 1 memo[l + r + 1] += 1 # Increment memo[max(l, r) + k + 1] by 1 memo[max(l, r) + k + 1] += 1 # Store the minimum number of moves ans = N curr = N # Find the prefix sum of memo[] for i in range(2, 2 * k + 1): curr += memo[i] # Update ans ans = min(ans, curr) # Prthe answer print (ans) # Driver Code if __name__ == '__main__': arr =[1, 2, 4, 3] K = 4 # Function Call minReplacements(arr, K) # This code is contributed by mohit kumar 29 |
C#
// C# program for the above approach using System; class GFG{ // Function to count the minimum replacements // required to make the sum of equidistant // array elements from the end equal static void minReplacements(int[] nums, int k) { // Store the size of nums array int N = nums.Length; // Initialize an auxiliary array int[] memo = new int[(k * 2 + 2)]; for(int i = 0; i < k * 2 + 2; ++i) { memo[i] = 0; } // Iterate nums in range[0, N/2-1] for(int i = 0; i < N / 2; ++i) { // Store the left element and // the right element int l = nums[i], r = nums[N - 1 - i]; // Decrement memo[min(l, r) + 1] by 1 --memo[(Math.Min(l, r) + 1)]; // Decrement memo[l + r] by 1 --memo[l + r]; // Increment memo[l + r + 1] by 1 ++memo[l + r + 1]; // Increment memo[max(l, r) + k + 1] by 1 ++memo[(Math.Max(l, r) + k + 1)]; } // Store the minimum number of moves int ans = N; int curr = N; // Find the prefix sum of memo[] for(int i = 2; i <= k * 2; ++i) { curr += memo[i]; // Update ans ans = Math.Min(ans, curr); } // Print the answer Console.WriteLine(ans); } // Driver code public static void Main() { int[] arr = { 1, 2, 4, 3 }; int K = 4; // Function Call minReplacements(arr, K); } } // This code is contributed by sanjoy_62 |
Javascript
<script> // Javascript program for the above approach // Function to count the minimum replacements // required to make the sum of equidistant // array elements from the end equal function minReplacements(nums, k) { // Store the size of nums array var N = nums.length; // Initialize an auxiliary array var memo = Array(k*2 +2).fill(0); // Iterate nums in range[0, N/2-1] for (var i = 0; i < N / 2; ++i) { // Store the left element and // the right element var l = nums[i], r = nums[N - 1 - i]; // Decrement memo[min(l, r) + 1] by 1 --memo[(Math.min(l, r) + 1)]; // Decrement memo[l + r] by 1 --memo[l + r]; // Increment memo[l + r + 1] by 1 ++memo[l + r + 1]; // Increment memo[max(l, r) + k + 1] by 1 ++memo[(Math.max(l, r) + k + 1)]; } // Store the minimum number of moves var ans = N; var curr = N; // Find the prefix sum of memo[] for (var i = 2; i <= k * 2; ++i) { curr += memo[i]; // Update ans ans = Math.min(ans, curr); } // Print the answer document.write( ans); } // Driver Code var arr = [ 1, 2, 4, 3 ]; var K = 4; // Function Call minReplacements(arr, K); </script> |
Output:
1
Time Complexity: O(N + K)
Auxiliary Space: O(K)
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!
