# Minimize swaps between two arrays such that sum of the first array exceeds sum of the second array

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:**

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the **DSA Self Paced Course** at a student-friendly price and become industry ready. To complete your preparation from learning a language to DS Algo and many more, please refer **Complete Interview Preparation Course****.**

In case you wish to attend **live classes **with experts, please refer **DSA Live Classes for Working Professionals **and **Competitive Programming Live for Students**.

Input:arr1[] = {1, 3, 2, 4}, arr2[] = {6, 7, 8}Output:1Explanation:

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**.

- Check if
- 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 Code` `int` `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;` `}` |

## Java

`// Java program for the above approach` `import` `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 Code` `arr1 ` `=` `[ ` `1` `, ` `3` `, ` `2` `, ` `4` `]` `arr2 ` `=` `[ ` `6` `, ` `7` `, ` `8` `]` `N ` `=` `len` `(arr1)` `M ` `=` `len` `(arr2)` `# Function Call` `print` `(maximumCount(arr1, arr2, N, M))` `# This code is contributed by sanjoy_62` |

## C#

`// C# program for the above approach` `using` `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)