Given 2 arrays of integers a[] and b[] with the same size of n (1 <= n <= 100) numbered from 1 to n.
(0 <= a[i], b[i] <= 6)
You can swap any a[i] with b[i].
What is the minimum number of swaps needed so that the difference of the sums of array a[] and b[] is minimum ?
Then print out:
Example
n = 6
a[] = { 1, 1, 4, 4, 0, 6 }
b[] = { 6, 3, 1, 1, 6, 1 }
Result
- 2 (The number of swaps)
- 5, 6 (The swapped indexes)
- 0 (The difference of sums of the arrays)
Explanation
If you swap a[5] with b[5] and a[6] with b[6] which requires 2 swaps, arrays a[] and b[] will become:
a[] = {1, 1, 4, 4, 6, 1}
b[] = {6, 3, 1, 1, 0, 6}
Sum of a[] is 1 + 1 + 4 + 4 + 6 + 1 = 17
Sum of b[] is 6 + 3 + 1 + 1 + 0 + 6 = 17
So the difference of the two sums is 0.
Short Explanation:
We maintain a mapping of all differences and their minimum swaps seen so far and try to extend all of the differences seen so far based on new values to get new mapping of such kind. We have 2 choices at each step when considering ith items in A and B, either consider the items as it is or swap the ith items.
Code:
#include <iostream>
#include <climits>
#include <unordered_map>
#include <vector>
using namespace std; // Pardon me for this sin
void update_keeping_existing_minimum(unordered_map<int, vector<int> >& mp, int key, vector<int>& value){
if(mp.find(key) == mp.end() || mp[key].size() > value.size())mp[key] = value;
}
// Prints minimum swaps, indexes of swaps and minimum difference of sums
// Runtime is O(2^size_of_input) = 2^1 + 2^2 .. + 2^n = 2*2^n
// This is a bruteforce implementation.
// We try all possible cases, by expanding our array 1 index at time.
// For each previous difference,
// we use new index value and expand our possible difference outcomes.
// In worst case we may get 2 unique differences never seen before for every index.
void get_minimum_swaps(vector<int>& a, vector<int>& b){
int n = a.size();
unordered_map<int, vector<int> > prv_differences_mp;
prv_differences_mp[0] = {}; // initial state
for(int i = 0 ; i < n ; i++){
unordered_map<int, vector<int> > new_differences_mp;
for (auto& it: prv_differences_mp) {
// possibility 1, we swap and expand previous difference
int d = it.first;
int d1 = d + b[i] - a[i];
if(prv_differences_mp.find(d1) != prv_differences_mp.end() && prv_differences_mp[d1].size() < (prv_differences_mp[d].size() + 1)){
update_keeping_existing_minimum(new_differences_mp, d1, prv_differences_mp[d1]);
} else {
// only place we are modifying the prv map, lets make a copy so that changes don't affect other calculations
vector<int> temp = prv_differences_mp[d];
temp.push_back(i+1);
update_keeping_existing_minimum(new_differences_mp, d1, temp);
}
// possibility 2, we don't swap and expand previous difference
int d2 = d + a[i] - b[i];
if(prv_differences_mp.find(d2) != prv_differences_mp.end() && prv_differences_mp[d2].size() < prv_differences_mp[d].size()){
update_keeping_existing_minimum(new_differences_mp, d2, prv_differences_mp[d2]);
} else {
update_keeping_existing_minimum(new_differences_mp, d2, prv_differences_mp[d]);
}
}
cout<<i<<":index\n";
for(auto& it: prv_differences_mp){
cout<<it.first<<": [ ";
for(auto& item: it.second)cout<<item<<" ";
cout<<"] ; ";
}
cout<<"\n";
prv_differences_mp = new_differences_mp;
}
int best = INT_MAX;
vector<int> min_swap_ans;
for(auto& it: prv_differences_mp){
int _d = it.first >= 0 ? it.first: -it.first;
if(_d < best){
best = _d;
min_swap_ans = it.second;
}
}
cout<<"Number of swaps: "<<min_swap_ans.size()<<"\n";
cout<<"Swapped indexes:\n";
for(auto idx: min_swap_ans)cout<<idx<<" ";
cout<<"\nDifference: "<<best<<"\n";
}
int main(){
vector<int> A{ 1, 1, 4, 4, 0, 6 };
vector<int> B{ 6, 3, 1, 1, 6, 1 };
get_minimum_swaps(A, B);
return 0;
}