Given a positive integer K and two arrays A[] and B[] consisting of M and N positive integers from the range [1, K] respectively, the task is to minimize the count of replacements of array elements by values from the range [1, K] such that the sum of elements of both the arrays becomes equal. If it is impossible to make the sum equal, then print -1.
Examples:
Input: K = 6, A[] = {3, 4, 1}, B[] = {6, 6, 6}
Output: 2
Explanation:
One of the possible way is to replace elements of array B[] at indexes 0 and 1 with 1 in two moves. Therefore, the array B[] modifies to {1, 1, 6}.
Now, the sum of both the arrays is 8, which is equal.Input: A[] = {4, 3, 2}, B[] = {2, 3, 3, 1}, K = 6, N = 4, M = 3
Output: 0
Approach: The given problem can be solved using Two-pointer technique. Follow the steps below to solve the problem:
- Initialize 4 variables, say l1 = 0, r1 = M – 1, l2 = 0, r2 = N – 1, used to traverse the array.
- Initialize a variable, say res, to store the count of minimum replacements required.
- Sort both the given arrays in ascending order.
- Find the difference of the sum of both arrays and store it in a variable, say diff.
- Iterate until l1 ? r1 or l2 ? r2 and perform the following steps:
- If diff = 0: Break out of the loop.
- If diff exceeds 0: Take the maximum between (A[r1] – 1) and (K – B[l2]) and subtract it from the difference diff and then increment l2, if the value of (K – B[l2]) is greater. Otherwise, decrement r1 by one.
- Otherwise, take the maximum between (B[r2] – 1) and (K – A[l1]) and add it to the difference diff, then increment l1, if (K – A[l1]) is greater. Otherwise, decrement the value of r2 by 1.
- Increment the value of res by 1.
- After completing the above steps, print the value of res as the minimum number of replacements of array elements required.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>using namespace std;// Function to find minimum number// of replacements required to make// the sum of two arrays equalint makeSumEqual(vector<int> a, vector<int> b, int K, int M, int N){ // Stores the sum of a[] int sum1 = 0; // Stores the sum of b[] int sum2 = 0; // Calculate sum of the array a[] for (int el : a) sum1 += el; // Calculate sum of the array b[] for (int el : b) sum2 += el; // Stores the difference // between a[] and b[] int diff = sum1 - sum2; // Left and Right pointer // to traverse the array a[] int l1 = 0, r1 = M - 1; // Left and Right pointer // to traverse the array b[] int l2 = 0, r2 = N - 1; // Stores the count of moves int res = 0; // Sort the arrays in // ascending order sort(a.begin(),a.end()); sort(b.begin(),b.end()); // Iterate while diff != 0 and // l1 <= r1 or l2 <= r2 while (l1 <= r1 || l2 <= r2) { if (diff == 0) { break; } // If diff is greater than 0 if (diff > 0) { // If all pointers are valid if (l2 <= r2 && l1 <= r1) { if (K - b[l2] < a[r1] - 1) { int sub = min( a[r1] - 1, diff); diff -= sub; a[r1] -= sub; r1--; } else { int sub = min( K - b[l2], diff); diff -= sub; b[l2] += sub; l2++; } } // Otherwise, if only pointers // of array a[] is valid else if (l1 <= r1) { int sub = min( a[r1] - 1, diff); diff -= sub; a[r1] -= sub; r1--; } // Otherwise else { int sub = min( K - b[l2], diff); diff -= sub; b[l2] += sub; l2++; } } // If diff is less than 0 else { // If all pointers are valid if (l1 <= r1 && l2 <= r2) { if (K - a[l1] < b[r2] - 1) { int sub = min( b[r2] - 1, -1 * diff); diff += sub; b[r2] -= sub; r2--; } else { int sub = min( K - a[l1], -1 * diff); diff += sub; a[l1] -= sub; l1++; } } // Otherwise, if only pointers // of array a[] is valid else if (l2 <= r2) { int sub = min( b[r2] - 1, -1 * diff); diff += sub; b[r2] -= sub; r2--; } // Otherwise else { int sub = min( K - a[l1], diff); diff += sub; a[l1] += sub; l1++; } } // Increment count // of res by one res++; } // If diff is 0, then return res if (diff == 0) return res; // Otherwise, return -1 else return -1;}// Driver Codeint main(){ vector<int> A = { 1, 4, 3 }; vector<int> B = { 6, 6, 6 }; int M = A.size(); int N = B.size(); int K = 6; cout << makeSumEqual(A, B, K,M, N); return 0;}// This code is contributed by mohit kumar 29. |
Java
// Java program for the above approachimport java.util.*;class GFG { // Function to find minimum number // of replacements required to make // the sum of two arrays equal public static int makeSumEqual( int[] a, int[] b, int K, int M, int N) { // Stores the sum of a[] int sum1 = 0; // Stores the sum of b[] int sum2 = 0; // Calculate sum of the array a[] for (int el : a) sum1 += el; // Calculate sum of the array b[] for (int el : b) sum2 += el; // Stores the difference // between a[] and b[] int diff = sum1 - sum2; // Left and Right pointer // to traverse the array a[] int l1 = 0, r1 = M - 1; // Left and Right pointer // to traverse the array b[] int l2 = 0, r2 = N - 1; // Stores the count of moves int res = 0; // Sort the arrays in // ascending order Arrays.sort(a); Arrays.sort(b); // Iterate while diff != 0 and // l1 <= r1 or l2 <= r2 while (l1 <= r1 || l2 <= r2) { if (diff == 0) { break; } // If diff is greater than 0 if (diff > 0) { // If all pointers are valid if (l2 <= r2 && l1 <= r1) { if (K - b[l2] < a[r1] - 1) { int sub = Math.min( a[r1] - 1, diff); diff -= sub; a[r1] -= sub; r1--; } else { int sub = Math.min( K - b[l2], diff); diff -= sub; b[l2] += sub; l2++; } } // Otherwise, if only pointers // of array a[] is valid else if (l1 <= r1) { int sub = Math.min( a[r1] - 1, diff); diff -= sub; a[r1] -= sub; r1--; } // Otherwise else { int sub = Math.min( K - b[l2], diff); diff -= sub; b[l2] += sub; l2++; } } // If diff is less than 0 else { // If all pointers are valid if (l1 <= r1 && l2 <= r2) { if (K - a[l1] < b[r2] - 1) { int sub = Math.min( b[r2] - 1, -1 * diff); diff += sub; b[r2] -= sub; r2--; } else { int sub = Math.min( K - a[l1], -1 * diff); diff += sub; a[l1] -= sub; l1++; } } // Otherwise, if only pointers // of array a[] is valid else if (l2 <= r2) { int sub = Math.min( b[r2] - 1, -1 * diff); diff += sub; b[r2] -= sub; r2--; } // Otherwise else { int sub = Math.min( K - a[l1], diff); diff += sub; a[l1] += sub; l1++; } } // Increment count // of res by one res++; } // If diff is 0, then return res if (diff == 0) return res; // Otherwise, return -1 else return -1; } // Driver Code public static void main(String[] args) { int[] A = { 1, 4, 3 }; int[] B = { 6, 6, 6 }; int M = A.length; int N = B.length; int K = 6; System.out.println( makeSumEqual(A, B, K, M, N)); }} |
Python3
# Python program for the above approach# Function to find minimum number# of replacements required to make# the sum of two arrays equalfrom functools import cmp_to_keydef cmp(c, d): return c - ddef makeSumEqual(a, b, K, M, N): # Stores the sum of a[] sum1 = 0 # Stores the sum of b[] sum2 = 0 # Calculate sum of the array a[] for el in range(len(a)): sum1 += a[el] # Calculate sum of the array b[] for el in range(len(b)): sum2 += b[el] # Stores the difference # between a[] and b[] diff = sum1 - sum2 # Left and Right pointer # to traverse the array a[] l1 = 0 r1 = M - 1 # Left and Right pointer # to traverse the array b[] l2 = 0 r2 = N - 1 # Stores the count of moves res = 0 # Sort the arrays in # ascending order a.sort(key=cmp_to_key(cmp)) b.sort(key=cmp_to_key(cmp)) # Iterate while diff != 0 and # l1 <= r1 or l2 <= r2 while(l1 <= r1 or l2 <= r2): if (diff == 0): break # If diff is greater than 0 if(diff > 0): # If all pointers are valid if(l2 <= r2 and l1 <= r1): if(K - b[l2] < a[r1] - 1): sub = min(a[r1] - 1, diff) diff -= sub a[r1] -= sub r1 -= 1 else: sub = min(K - b[l2], diff) diff -= sub b[l2] += sub l2 += 1 # Otherwise, if only pointers # of array a[] is valid elif(l1 <= r1): sub = min(a[r1] - 1, diff) diff -= sub a[r1] -= sub r1 -= 1 # Otherwise else: sub = min(K - b[l2], diff) diff -= sub b[l2] += sub l2 += 1 # If diff is less than 0 else: # If all pointers are valid if(l1 <= r1 and l2 <= r2): if (K - a[l1]< b[r2] - 1): sub = min(b[r2] - 1,-1 * diff) diff += sub b[r2] -= sub r2 -= 1 else: sub = min(K - a[l1],-1 * diff) diff += sub a[l1] -= sub l1 += 1 # Otherwise, if only pointers # of array a[] is valid elif(l2 <= r2): sub = min(b[r2] - 1,-1 * diff) diff += sub b[r2] -= sub r2 -= 1 # Otherwise else: sub = min(K - a[l1], diff) diff += sub a[l1] += sub l1 += 1 # Increment count # of res by one res += 1 # If diff is 0, then return res if (diff == 0): return res # Otherwise, return -1 else: return -1# Driver CodeA=[1, 4, 3 ]B=[6, 6, 6 ]M = len(A)N = len(B)K = 6print(makeSumEqual(A, B, K,M, N))# This code is contributed by shinjanpatra |
C#
// C# program to implement// the above approachusing System;public class GFG{ // Function to find minimum number // of replacements required to make // the sum of two arrays equal public static int makeSumEqual( int[] a, int[] b, int K, int M, int N) { // Stores the sum of a[] int sum1 = 0; // Stores the sum of b[] int sum2 = 0; // Calculate sum of the array a[] foreach (int el in a) sum1 += el; // Calculate sum of the array b[] foreach (int el in b) sum2 += el; // Stores the difference // between a[] and b[] int diff = sum1 - sum2; // Left and Right pointer // to traverse the array a[] int l1 = 0, r1 = M - 1; // Left and Right pointer // to traverse the array b[] int l2 = 0, r2 = N - 1; // Stores the count of moves int res = 0; // Sort the arrays in // ascending order Array.Sort(a); Array.Sort(b); // Iterate while diff != 0 and // l1 <= r1 or l2 <= r2 while (l1 <= r1 || l2 <= r2) { if (diff == 0) { break; } // If diff is greater than 0 if (diff > 0) { // If all pointers are valid if (l2 <= r2 && l1 <= r1) { if (K - b[l2] < a[r1] - 1) { int sub = Math.Min( a[r1] - 1, diff); diff -= sub; a[r1] -= sub; r1--; } else { int sub = Math.Min( K - b[l2], diff); diff -= sub; b[l2] += sub; l2++; } } // Otherwise, if only pointers // of array a[] is valid else if (l1 <= r1) { int sub = Math.Min( a[r1] - 1, diff); diff -= sub; a[r1] -= sub; r1--; } // Otherwise else { int sub = Math.Min( K - b[l2], diff); diff -= sub; b[l2] += sub; l2++; } } // If diff is less than 0 else { // If all pointers are valid if (l1 <= r1 && l2 <= r2) { if (K - a[l1] < b[r2] - 1) { int sub = Math.Min( b[r2] - 1, -1 * diff); diff += sub; b[r2] -= sub; r2--; } else { int sub = Math.Min( K - a[l1], -1 * diff); diff += sub; a[l1] -= sub; l1++; } } // Otherwise, if only pointers // of array a[] is valid else if (l2 <= r2) { int sub = Math.Min( b[r2] - 1, -1 * diff); diff += sub; b[r2] -= sub; r2--; } // Otherwise else { int sub = Math.Min( K - a[l1], diff); diff += sub; a[l1] += sub; l1++; } } // Increment count // of res by one res++; } // If diff is 0, then return res if (diff == 0) return res; // Otherwise, return -1 else return -1; }// Driver Codepublic static void Main(String[] args){ int[] A = { 1, 4, 3 }; int[] B = { 6, 6, 6 }; int M = A.Length; int N = B.Length; int K = 6; Console.WriteLine( makeSumEqual(A, B, K, M, N));}} |
Javascript
<script>// Javascript program for the above approach// Function to find minimum number// of replacements required to make// the sum of two arrays equalfunction makeSumEqual(a,b,K,M,N){ // Stores the sum of a[] let sum1 = 0; // Stores the sum of b[] let sum2 = 0; // Calculate sum of the array a[] for (let el=0;el< a.length;el++) sum1 += a[el]; // Calculate sum of the array b[] for (let el=0;el< b.length;el++) sum2 += b[el]; // Stores the difference // between a[] and b[] let diff = sum1 - sum2; // Left and Right pointer // to traverse the array a[] let l1 = 0, r1 = M - 1; // Left and Right pointer // to traverse the array b[] let l2 = 0, r2 = N - 1; // Stores the count of moves let res = 0; // Sort the arrays in // ascending order a.sort(function(c,d){return c-d;}); b.sort(function(c,d){return c-d;}); // Iterate while diff != 0 and // l1 <= r1 or l2 <= r2 while (l1 <= r1 || l2 <= r2) { if (diff == 0) { break; } // If diff is greater than 0 if (diff > 0) { // If all pointers are valid if (l2 <= r2 && l1 <= r1) { if (K - b[l2] < a[r1] - 1) { let sub = Math.min( a[r1] - 1, diff); diff -= sub; a[r1] -= sub; r1--; } else { let sub = Math.min( K - b[l2], diff); diff -= sub; b[l2] += sub; l2++; } } // Otherwise, if only pointers // of array a[] is valid else if (l1 <= r1) { let sub = Math.min( a[r1] - 1, diff); diff -= sub; a[r1] -= sub; r1--; } // Otherwise else { let sub = Math.min( K - b[l2], diff); diff -= sub; b[l2] += sub; l2++; } } // If diff is less than 0 else { // If all pointers are valid if (l1 <= r1 && l2 <= r2) { if (K - a[l1] < b[r2] - 1) { let sub = Math.min( b[r2] - 1, -1 * diff); diff += sub; b[r2] -= sub; r2--; } else { let sub = Math.min( K - a[l1], -1 * diff); diff += sub; a[l1] -= sub; l1++; } } // Otherwise, if only pointers // of array a[] is valid else if (l2 <= r2) { let sub = Math.min( b[r2] - 1, -1 * diff); diff += sub; b[r2] -= sub; r2--; } // Otherwise else { let sub = Math.min( K - a[l1], diff); diff += sub; a[l1] += sub; l1++; } } // Increment count // of res by one res++; } // If diff is 0, then return res if (diff == 0) return res; // Otherwise, return -1 else return -1;}// Driver Codelet A=[1, 4, 3 ];let B=[6, 6, 6 ];let M = A.length;let N = B.length;let K = 6;document.write(makeSumEqual(A, B, K, M, N));// This code is contributed by unknown2108</script> |
Output:
2
Time Complexity: O(N*log(N)+M*log(M))
Auxiliary Space: O(1)
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!
