Given two arrays arr1[] and arr2[] of size N and M respectively, the task is to count the minimum number of swaps required between the two arrays in order to make the sum of the array arr1[] greater than the arr2[].
Examples:
Input: arr1[] = {1, 3, 2, 4}, arr2[] = {6, 7, 8}
Output: 1
Explanation:
Swapping arr1[0] with arr2[2] makes the sum of arr1[] equal to 17, which is greater than 14.
Therefore, the count of swaps required is 1.Input: arr1[] = {2, 2}, arr2[] = {5, 5, 5}
Output: 2
Approach: The given problem can be solved by sorting both the arrays and perform the swaps to get maximize the sum of arr1[]. Follow the steps below to solve the problem:
- Sort both the arrays and compute the sum of the arrays as sum1 and sum2 respectively.
- Initialize a variable count as 0 to store the count of swaps required and j to (M – 1) to point to the last element of the array arr2[].
- Traverse the array the arr1[] using the variable i and perform the following steps:
- Check if sum1 is less than or equal to sum2, then swap the current element arr[i] with the element arr2[j] to maximize sum1.
- After swapping, update the value of sum1, sum2, and decrement j to point to the next to last element and increment count.
- After completing the above steps, print the value of count as the minimum count of swaps required.
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 the minimum count of swaps required// between the two arrays to make the sum of arr1[] greater// than that of arr2[]int maximumCount(int arr1[], int arr2[], int s1, int s2){ // Stores the sum of the two arrays int sum1 = 0, sum2 = 0; // Calculate sum of arr1[] for (int i = 0; i < s1; i++) sum1 += arr1[i]; // Calculate sum of arr2[] for (int j = 0; j < s2; j++) sum2 += arr2[j]; int len = 0; if (s1 >= s2) len = s2; else len = s1; // Sort the arrays arr1[] and arr2[] sort(arr1, arr1 + s1); sort(arr2, arr2 + s2); int j = 0, k = s2 - 1, count = 0; // Traverse the array arr[] for (int i = 0; i < len; i++) { // If the sum1 is less than or equal to sum2 if (sum1 <= sum2) { // Swapping the elements if (arr2[k] >= arr1[i]) { // Update the sum1 and sum2 int dif1 = arr1[j], dif2 = arr2[k]; sum1 -= dif1; sum1 += dif2; sum2 -= dif2; sum2 += dif1; j++; k--; // Increment the count count++; } else break; } else break; } // Return the final count return count;}// Driver Codeint main(){ int arr1[] = { 1, 3, 2, 4 }; int arr2[] = { 6, 7, 8 }; int N = sizeof(arr1) / sizeof(arr1[0]); int M = sizeof(arr2) / sizeof(arr2[0]); // Function Call cout << maximumCount(arr1, arr2, N, M); return 0;} |
C
// C program for the above approach#include <stdio.h>#include <stdlib.h>// Compare function for qsortint cmpfunc(const void* a, const void* b){ return (*(int*)a - *(int*)b);}// Function to find the minimum count of swaps required// between the two arrays to make the sum of arr1[] greater// than that of arr2[]int maximumCount(int arr1[], int arr2[], int s1, int s2){ // Stores the sum of the two arrays int sum1 = 0, sum2 = 0; // Calculate sum of arr1[] for (int i = 0; i < s1; i++) sum1 += arr1[i]; // Calculate sum of arr2[] for (int j = 0; j < s2; j++) sum2 += arr2[j]; int len = 0; if (s1 >= s2) len = s2; else len = s1; // Sort the arrays arr1[] and arr2[] qsort(arr1, s1, sizeof(int), cmpfunc); qsort(arr2, s2, sizeof(int), cmpfunc); int j = 0, k = s2 - 1, count = 0; // Traverse the array arr[] for (int i = 0; i < len; i++) { // If the sum1 is less than or equal to sum2 if (sum1 <= sum2) { // Swapping the elements if (arr2[k] >= arr1[i]) { // Update the sum1 and sum2 int dif1 = arr1[j], dif2 = arr2[k]; sum1 -= dif1; sum1 += dif2; sum2 -= dif2; sum2 += dif1; j++; k--; // Increment the count count++; } else break; } else break; } // Return the final count return count;}// Driver Codeint main(){ int arr1[] = { 1, 3, 2, 4 }; int arr2[] = { 6, 7, 8 }; int N = sizeof(arr1) / sizeof(arr1[0]); int M = sizeof(arr2) / sizeof(arr2[0]); // Function Call printf("%d", maximumCount(arr1, arr2, N, M)); return 0;}// This code is contributed by Sania Kumari Gupta |
Java
// Java program for the above approachimport java.io.*;import java.util.*;class GFG { // Function to find the minimum count // of swaps required between the two // arrays to make the sum of arr1[] // greater than that of arr2[] static int maximumCount(int[] arr1, int[] arr2, int s1, int s2) { // Stores the sum of the two arrays int sum1 = 0, sum2 = 0; // Calculate sum of arr1[] for (int i = 0; i < s1; i++) { sum1 += arr1[i]; } // Calculate sum of arr2[] for (int j = 0; j < s2; j++) { sum2 += arr2[j]; } int len = 0; if (s1 >= s2) { len = s2; } else { len = s1; } // Sort the arrays arr1[] and arr2[] Arrays.sort(arr1); Arrays.sort(arr2); int j = 0, k = s2 - 1, count = 0; // Traverse the array arr[] for (int i = 0; i < len; i++) { // If the sum1 is less than // or equal to sum2 if (sum1 <= sum2) { // Swapping the elements if (arr2[k] >= arr1[i]) { // Update the sum1 and sum2 int dif1 = arr1[j], dif2 = arr2[k]; sum1 -= dif1; sum1 += dif2; sum2 -= dif2; sum2 += dif1; j++; k--; // Increment the count count++; } else { break; } } else { break; } } // Return the final count return count; } // Driver Code public static void main(String[] args) { int[] arr1 = new int[] { 1, 3, 2, 4 }; int[] arr2 = new int[] { 6, 7, 8 }; int N = arr1.length; int M = arr2.length; // Function Call System.out.println(maximumCount(arr1, arr2, N, M)); }}// This code is contributed by dharanendralv23 |
Python3
# Python3 program to implement# the above approach# Function to find the minimum count# of swaps required between the two# arrays to make the sum of arr1[]# greater than that of arr2[]def maximumCount(arr1, arr2, s1, s2) : # Stores the sum of the two arrays sum1 = 0 sum2 = 0 # Calculate sum of arr1[] for i in range(s1): sum1 += arr1[i] # Calculate sum of arr2[] for j in range(s2): sum2 += arr2[j] len = 0 if (s1 >= s2) : lenn = s2 else : lenn = s1 # Sort the arrays arr1[] and arr2[] arr1.sort(); arr2.sort(); j = 0 k = s2 - 1 count = 0 # Traverse the array arr[] for i in range(lenn): # If the sum1 is less than # or equal to sum2 if (sum1 <= sum2) : # Swapping the elements if (arr2[k] >= arr1[i]) : # Update the sum1 and sum2 dif1 = arr1[j] dif2 = arr2[k] sum1 -= dif1 sum1 += dif2 sum2 -= dif2 sum2 += dif1 j += 1 k -= 1 # Increment the count count += 1 else : break else : break # Return the final count return count# Driver Codearr1 = [ 1, 3, 2, 4 ]arr2 = [ 6, 7, 8 ]N = len(arr1) M = len(arr2) # Function Callprint(maximumCount(arr1, arr2, N, M))# This code is contributed by sanjoy_62 |
C#
// C# program for the above approachusing System;class GFG { // Function to find the minimum count // of swaps required between the two // arrays to make the sum of arr1[] // greater than that of arr2[] static int maximumCount(int[] arr1, int[] arr2, int s1, int s2) { // Stores the sum of the two arrays int sum1 = 0, sum2 = 0; // Calculate sum of arr1[] for (int i = 0; i < s1; i++) { sum1 += arr1[i]; } // Calculate sum of arr2[] for (int a = 0; a < s2; a++) { sum2 += arr2[a]; } int len = 0; if (s1 >= s2) { len = s2; } else { len = s1; } // Sort the arrays arr1[] and arr2[] Array.Sort(arr1); Array.Sort(arr2); int j = 0, k = s2 - 1, count = 0; // Traverse the array arr[] for (int i = 0; i < len; i++) { // If the sum1 is less than // or equal to sum2 if (sum1 <= sum2) { // Swapping the elements if (arr2[k] >= arr1[i]) { // Update the sum1 and sum2 int dif1 = arr1[j], dif2 = arr2[k]; sum1 -= dif1; sum1 += dif2; sum2 -= dif2; sum2 += dif1; j++; k--; // Increment the count count++; } else { break; } } else { break; } } // Return the final count return count; } // Driver Code static public void Main() { int[] arr1 = new int[] { 1, 3, 2, 4 }; int[] arr2 = new int[] { 6, 7, 8 }; int N = arr1.Length; int M = arr2.Length; // Function Call Console.WriteLine(maximumCount(arr1, arr2, N, M)); }}// This code is contributed by dharanendralv23 |
Javascript
<script>// Javascript program of the above approach // Function to find the minimum count // of swaps required between the two // arrays to make the sum of arr1[] // greater than that of arr2[] function maximumCount( arr1, arr2, s1, s2) { // Stores the sum of the two arrays let sum1 = 0, sum2 = 0; // Calculate sum of arr1[] for (let i = 0; i < s1; i++) { sum1 += arr1[i]; } // Calculate sum of arr2[] for (let j = 0; j < s2; j++) { sum2 += arr2[j]; } let len = 0; if (s1 >= s2) { len = s2; } else { len = s1; } // Sort the arrays arr1[] and arr2[] arr1.sort(); arr2.sort(); let j = 0, k = s2 - 1, count = 0; // Traverse the array arr[] for (let i = 0; i < len; i++) { // If the sum1 is less than // or equal to sum2 if (sum1 <= sum2) { // Swapping the elements if (arr2[k] >= arr1[i]) { // Update the sum1 and sum2 let dif1 = arr1[j], dif2 = arr2[k]; sum1 -= dif1; sum1 += dif2; sum2 -= dif2; sum2 += dif1; j++; k--; // Increment the count count++; } else { break; } } else { break; } } // Return the final count return count; } // Driver Code let arr1 = [ 1, 3, 2, 4 ]; let arr2 = [ 6, 7, 8 ]; let N = arr1.length; let M = arr2.length; // Function Call document.write(maximumCount(arr1, arr2, N, M)); </script> |
Output:
1
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!
