Minimize replacements by integers up to K to make the sum of equidistant array elements from the end equal
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> |
1
Time Complexity: O(N + K)
Auxiliary Space: O(K)