Minimize swap of elements such that one Array has greater sum than other
Given two arrays A[] and B[] with size N and M, the task is to find the minimum number of swaps between two arrays (can be any two element of two arrays) required to make the sum of array A[] strictly greater than array B[].
Examples:
Input: N = 5, A[] = {1, 5, 4, 6, 2}, M = 7, B[] = {0, 1, 17, 4, 6, 2, 9}
Output: 1
Explanation: In the given example, to make A[] strictly greater:
Firstly, swap 0th index element from A[] with 2nd index element from B[].
After that, sum of array A[] is 17+5+4+6+2 = 34 and
sum of array B is 0+1+1+4+6+2+9=23.
Thus, sum of array A[] is greater than sum of array B[] by performing only 1 swap.Input: N = 5, A[] = {5, 6, 7, 8, 9} , M = 5, B[] = {0, 1, 2, 3, 4}
Output: 0
Explanation: As, the sum of array A[] is greater than sum of array B[].
Hence, no swap between the arrays is required.
Approach: The problem can be solved based on the following idea:
To minimize the number of operations, the most optimal choice is to swap the minimum elements of array A[] with maximum elements of array B[].
Follow the steps to solve the problem:
- Sort array A[] in increasing order and array B[] in decreasing order.
- Calculate the sum of both arrays.
- If the sum of array A[] is greater than the sum of array B[] then return 0.
- Otherwise, swap maximum element from array B[] and minimum element from array A[] until sum of A[] is not greater than B[].
- Return the number of operations required to make array A[] strictly greater than array B[].
- If not possible, return -1.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to find minimum operation int minimumopretion( int A[], int N, int B[], int M) { sort(A, A + N); sort(B, B + M, greater< int >()); // Calculate sum of both array int suma = 0, sumb = 0; for ( int i = 0; i < N; i++) { suma += A[i]; } for ( int i = 0; i < M; i++) { sumb += B[i]; } int count = 0, flag = 0; // If sum of array A is strictly // greater than sum of array B then // no need to do anything if (suma > sumb) { return 0; } else { // Find min size out of // both array size int x = min(M, N); // Swapping elements more formally // add element in array A from B // and add element in array B // from array A for ( int i = 0; i < x; i++) { suma += (B[i] - A[i]); sumb += (A[i] - B[i]); // Count number of operation count++; // If sum of array A is strictly // greater than array B // break the loop if (suma > sumb) break ; } // Check whether it is possible // to make sum of array A // is strictly greater than array B if (suma <= sumb) return -1; else return count; } } // Driver Code int main() { int A[] = { 1, 5, 4, 6, 2 }; int B[] = { 0, 1, 17, 4, 6, 2, 9 }; int N = sizeof (A) / sizeof (A[0]); int M = sizeof (B) / sizeof (B[0]); cout << minimumopretion(A, N, B, M); return 0; } |
Java
// Java program for the above approach import java.util.*; class GFG { public static void reverse( int [] array) { // Length of the array int n = array.length; // Swapping the first half elements with last half // elements for ( int i = 0 ; i < n / 2 ; i++) { // Storing the first half elements temporarily int temp = array[i]; // Assigning the first half to the last half array[i] = array[n - i - 1 ]; // Assigning the last half to the first half array[n - i - 1 ] = temp; } } // Function to find minimum operation static int minimumopretion( int [] A, int N, int [] B, int M) { Arrays.sort(A); Arrays.sort(B); reverse(B); // Calculate sum of both array int suma = 0 , sumb = 0 ; for ( int i = 0 ; i < N; i++) { suma += A[i]; } for ( int i = 0 ; i < M; i++) { sumb += B[i]; } int count = 0 , flag = 0 ; // If sum of array A is strictly // greater than sum of array B then // no need to do anything if (suma > sumb) { return 0 ; } else { // Find min size out of // both array size int x = Math.min(M, N); // Swapping elements more formally // add element in array A from B // and add element in array B // from array A for ( int i = 0 ; i < x; i++) { suma += (B[i] - A[i]); sumb += (A[i] - B[i]); // Count number of operation count++; // If sum of array A is strictly // greater than array B // break the loop if (suma > sumb) break ; } // Check whether it is possible // to make sum of array A // is strictly greater than array B if (suma <= sumb) return - 1 ; else return count; } } // Driver Code public static void main (String[] args) { int A[] = { 1 , 5 , 4 , 6 , 2 }; int B[] = { 0 , 1 , 17 , 4 , 6 , 2 , 9 }; int N = A.length; int M = B.length; System.out.print(minimumopretion(A, N, B, M)); } } // This code is contributed by hrithikgarg03188. |
Python3
# python3 program for the above approach # Function to find minimum operation from audioop import reverse def minimumopretion(A, N, B, M): A.sort() B.sort(reverse = True ) # Calculate sum of both array suma, sumb = 0 , 0 for i in range ( 0 , N): suma + = A[i] for i in range ( 0 , M): sumb + = B[i] count, flag = 0 , 0 # If sum of array A is strictly # greater than sum of array B then # no need to do anything if (suma > sumb): return 0 else : # Find min size out of # both array size x = min (M, N) # Swapping elements more formally # add element in array A from B # and add element in array B # from array A for i in range ( 0 , x): suma + = (B[i] - A[i]) sumb + = (A[i] - B[i]) # Count number of operation count + = 1 # If sum of array A is strictly # greater than array B # break the loop if (suma > sumb): break # Check whether it is possible # to make sum of array A # is strictly greater than array B if (suma < = sumb): return - 1 else : return count # Driver Code if __name__ = = "__main__" : A = [ 1 , 5 , 4 , 6 , 2 ] B = [ 0 , 1 , 17 , 4 , 6 , 2 , 9 ] N = len (A) M = len (B) print (minimumopretion(A, N, B, M)) # This code is contributed by rakeshsahni |
C#
// C# program for the above approach using System; class GFG { // Function to find minimum operation static int minimumopretion( int [] A, int N, int [] B, int M) { Array.Sort(A); Array.Sort< int >( B, delegate ( int m, int n) { return n - m; }); // Calculate sum of both array int suma = 0, sumb = 0; for ( int i = 0; i < N; i++) { suma += A[i]; } for ( int i = 0; i < M; i++) { sumb += B[i]; } int count = 0, flag = 0; // If sum of array A is strictly // greater than sum of array B then // no need to do anything if (suma > sumb) { return 0; } else { // Find min size out of // both array size int x = Math.Min(M, N); // Swapping elements more formally // add element in array A from B // and add element in array B // from array A for ( int i = 0; i < x; i++) { suma += (B[i] - A[i]); sumb += (A[i] - B[i]); // Count number of operation count++; // If sum of array A is strictly // greater than array B // break the loop if (suma > sumb) break ; } // Check whether it is possible // to make sum of array A // is strictly greater than array B if (suma <= sumb) return -1; else return count; } } // Driver Code public static void Main() { int [] A = { 1, 5, 4, 6, 2 }; int [] B = { 0, 1, 17, 4, 6, 2, 9 }; int N = A.Length; int M = B.Length; Console.Write(minimumopretion(A, N, B, M)); } } // This code is contributed by Samim Hossain Mondal. |
Javascript
<script> // JavaScript code for the above approach // Function to find minimum operation function minimumopretion(A, N, B, M) { A.sort(); B.sort( function (a, b) { return b - a }) // Calculate sum of both array let suma = 0, sumb = 0; for (let i = 0; i < N; i++) { suma += A[i]; } for (let i = 0; i < M; i++) { sumb += B[i]; } let count = 0, flag = 0; // If sum of array A is strictly // greater than sum of array B then // no need to do anything if (suma > sumb) { return 0; } else { // Find min size out of // both array size let x = Math.min(M, N); // Swapping elements more formally // add element in array A from B // and add element in array B // from array A for (let i = 0; i < x; i++) { suma += (B[i] - A[i]); sumb += (A[i] - B[i]); // Count number of operation count++; // If sum of array A is strictly // greater than array B // break the loop if (suma > sumb) break ; } // Check whether it is possible // to make sum of array A // is strictly greater than array B if (suma <= sumb) return -1; else return count; } } // Driver Code let A = [1, 5, 4, 6, 2]; let B = [0, 1, 17, 4, 6, 2, 9]; let N = A.length; let M = B.length; document.write(minimumopretion(A, N, B, M)); // This code is contributed by Potta Lokesh </script> |
1
Time Complexity: O(N* log N)
Auxiliary Space: O(1)
Another Approach:
- Start by declaring the function minimumOperation with input parameters A, N, B, and M.
- Initialize variables sumA and sumB to zero.
- Use a for loop to iterate through each element of array A and add its value to sumA.
- Use another for loop to iterate through each element of array B and add its value to sumB.
- If sumA is greater than sumB, return 0 as no operation is required.
- Sort the array A in ascending order using the sort function.
- Sort the array B in descending order using the sort function and passing greater<int>() as the second argument.
- Initialize variables i, j, and count to zero.
- Use a while loop to iterate through each element of arrays A and B.
- Compute the difference between the j-th element of B and the i-th element of A and store it in variable diff.
- If diff is less than or equal to zero, move to the next element of A by incrementing i.
- If diff is greater than zero, increment count, as a swap operation is required. Also, update the values of sumA and sumB accordingly.
- Move to the next element of both A and B by incrementing i and j.
- Check if sumA is greater than sumB. If so, return count as the minimum number of operations required to make the sum of A greater than B.
- If the end of the loop is reached and sumA is still less than or equal to sumB, return -1 as it is not possible to make the sum of A greater than B.
- Finally, in the main function, declare arrays A and B with sample values and compute their sizes N and M, respectively.
- Call the minimumOperation function with input parameters A, N, B, and M, and output the result.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h> using namespace std; int minimumOperation( int A[], int N, int B[], int M) { int sumA = 0, sumB = 0; for ( int i = 0; i < N; i++) { sumA += A[i]; } for ( int i = 0; i < M; i++) { sumB += B[i]; } if (sumA > sumB) { return 0; // no need to perform any operation } sort(A, A + N); sort(B, B + M, greater< int >()); int i = 0, j = 0, count = 0; while (i < N && j < M) { int diff = B[j] - A[i]; if (diff <= 0) { // A[i] is already greater than B[j], move to next element in A i++; } else { count++; // perform swap sumA += diff; sumB -= diff; i++; j++; if (sumA > sumB) { return count; } } } return -1; // it is not possible to make sum of A greater than B } int main() { int A[] = { 1, 5, 4, 6, 2 }; int B[] = { 0, 1, 17, 4, 6, 2, 9 }; int N = sizeof (A) / sizeof (A[0]); int M = sizeof (B) / sizeof (B[0]); cout << minimumOperation(A, N, B, M) << endl; return 0; } |
Java
// Java program for the above approach import java.util.Arrays; public class GFG { public static int minimumOperation( int [] A, int [] B) { int N = A.length; int M = B.length; int sumA = 0 ; int sumB = 0 ; // Calculate the sum of elements in lists A and B for ( int num : A) { sumA += num; } for ( int num : B) { sumB += num; } // If the sum of A is already greater than the sum of B, return 0 if (sumA > sumB) { return 0 ; } // Sort A in ascending order and B in descending order Arrays.sort(A); Arrays.sort(B); reverse(B); int i = 0 ; int j = 0 ; int count = 0 ; // Perform the swapping operation until the sum of A becomes greater than the sum of B while (i < N && j < M) { int diff = B[j] - A[i]; if (diff <= 0 ) { i++; // A[i] is already greater than B[j], move to the next element in A } else { count++; // Perform the swap operation sumA += diff; sumB -= diff; i++; j++; if (sumA > sumB) { return count; } } } // It is not possible to make the sum of A greater than B return - 1 ; } // Helper function to reverse the elements of an array in place private static void reverse( int [] arr) { int left = 0 ; int right = arr.length - 1 ; while (left < right) { int temp = arr[left]; arr[left] = arr[right]; arr[right] = temp; left++; right--; } } //Driver code public static void main(String[] args) { int [] A = { 1 , 5 , 4 , 6 , 2 }; int [] B = { 0 , 1 , 17 , 4 , 6 , 2 , 9 }; System.out.println(minimumOperation(A, B)); } } |
Python3
def minimum_operation(A, B): N = len (A) M = len (B) sumA = sum (A) sumB = sum (B) if sumA > sumB: return 0 # no need to perform any operation A.sort() B.sort(reverse = True ) i = 0 j = 0 count = 0 while i < N and j < M: diff = B[j] - A[i] if diff < = 0 : i + = 1 # A[i] is already greater than B[j], move to next element in A else : count + = 1 # perform swap sumA + = diff sumB - = diff i + = 1 j + = 1 if sumA > sumB: return count return - 1 # it is not possible to make sum of A greater than B A = [ 1 , 5 , 4 , 6 , 2 ] B = [ 0 , 1 , 17 , 4 , 6 , 2 , 9 ] print (minimum_operation(A, B)) |
C#
using System; class GFG { // Function to find the minimum number of the operations required static int MinimumOperation( int [] A, int N, int [] B, int M) { int sumA = 0, sumB = 0; // Calculate the sum of elements in arrays A and B for ( int i = 0; i < N; i++) { sumA += A[i]; } for ( int i = 0; i < M; i++) { sumB += B[i]; } // If the sum of A is already greater than sum of B // no need to perform any operation if (sumA > sumB) { return 0; } // Sort array A in ascending order Array.Sort(A); // Sort array B in descending order Array.Sort(B, (a, b) => b.CompareTo(a)); int indexA = 0, indexB = 0, count = 0; // Perform operations until the sum of a becomes greater than the sum of B while (indexA < N && indexB < M) { int diff = B[indexB] - A[indexA]; if (diff <= 0) { // A[indexA] is already greater than B[indexB] // move to the next element in A indexA++; } else { // Perform swap operation count++; sumA += diff; sumB -= diff; indexA++; indexB++; // Check if the sum of the becomes greater than the sum of B if (sumA > sumB) { return count; } } } return -1; } // Main method static void Main() { // Input arrays int [] A = { 1, 5, 4, 6, 2 }; int [] B = { 0, 1, 17, 4, 6, 2, 9 }; int N = A.Length; int M = B.Length; // Call the function and print the result Console.WriteLine(MinimumOperation(A, N, B, M)); } } |
Javascript
function GFG(A, N, B, M) { let sumA = 0, sumB = 0; // Calculate the sum of elements in arrays A and B for (let i = 0; i < N; i++) { sumA += A[i]; } for (let i = 0; i < M; i++) { sumB += B[i]; } // If the sum of A is already greater than or // equal to B, no operation needed if (sumA >= sumB) { return 0; } // Sort arrays A and B A.sort((a, b) => a - b); B.sort((a, b) => b - a); let i = 0, j = 0, count = 0; // Perform operations to make the sum of A greater than or equal to B while (i < N && j < M) { let diff = B[j] - A[i]; if (diff <= 0) { // A[i] is already greater than or equal to B[j] // move to the next element in A i++; } else { // Perform swap count++; sumA += diff; sumB -= diff; i++; j++; // If the sum of A becomes greater than or // equal to B, return the count if (sumA >= sumB) { return count; } } } // It is not possible to make the sum of // A greater than or equal to B return -1; } // Driver code let A = [1, 5, 4, 6, 2]; let B = [0, 1, 17, 4, 6, 2, 9]; let N = A.length; let M = B.length; console.log(GFG(A, N, B, M)); |
1
Time Complexity: O(n*logn)
Auxiliary Space: O(n+m)
Contact Us