**PROBLEM LINK**

**DIFFICULTY**

Easy

**PREREQUISITES**

Sorting

**PROBLEM IN SHORT**

Given two arrays, by doing a maximum of k swaps between them, reduce the sum of the maximum element of the two arrays.

**SOLUTION**

The key observation in this problem is that the maximum number between the two arrays will

always be included in the sum. This is because, however many swaps you do, it will still be a part

of either of the arrays.

Building up on this, we first choose an array that should contain the biggest element. Now the array

containing this biggest element should have all the other large elements. This is because the other

elements of the array won’t be part of the sum.

Hence, we simply swap the largest element from the other array with the smallest element of this

array, if it is bigger. We do this upto k times.

This can be done by sorting the two arrays (say big and small), and maintaining two pointers,

bigPt, and smallPt. Initially, bigPt = 0, & smallPt = n - 1. Now, after ever swap of big[bigPt] and

small[smallPt], bigPt is incremented by 1, and smallPt is decreased by 1.

Finally, once this is done - we sort the arrays once again, and big[n - 1] + small[n - 1] is the

solution.

**TIME COMPLEXITY**

O(n log n) for sorting, and O(n) for swaps, which means the overall time complexity is O(n log n).

**EDITORIALIST’s SOLUTION**

```
#include <bits/stdc++.h>
using namespace std;
int n, k;
int solve(vector<int> big, vector<int> small) {
int ck = k;
int smallPt = n - 1;
int bigPt = 0;
while (ck > 0) {
if (big[bigPt] >= small[smallPt])
break;
else if(bigPt >= n || smallPt < 0)
break;
else {
ck--;
swap(big[bigPt], small[smallPt]);
bigPt++;
smallPt--;
}
}
sort(big.begin(), big.end());
sort(small.begin(), small.end());
return big[n - 1] + small[n - 1];
}
int main() {
vector<int> a, b;
scanf("%d %d", &n, &k);
for (int i = 0; i < n; i++) {
int x;
scanf("%d", &x);
a.push_back(x);
}
for (int i = 0; i < n; i++) {
int x;
scanf("%d", &x);
b.push_back(x);
}
sort(a.begin(), a.end());
sort(b.begin(), b.end());
printf("%d", min( solve(a, b), solve(b, a) ) );
return 0;
}
```