What is the minimum number of swaps needed so that the difference of sums of arrays a and b is minimum?

user_9920930 0
Viewed 667

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:

  • The number of swaps
  • The swapped indexes
  • The difference of sums of both arrays

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.

np-hard arrays algorithm
2 Answers

Here's an iterative method that saves the differences so far and updates the smallest list of indexes needed to swap to achieve them.

JavaScript code:

function update(obj, d, arr){
  if (!obj[d] || obj[d].length > arr.length)
    obj[d] = arr;
}

function f(A, B){
  let diffs = {0: []};
  
  for (let i=0; i<A.length; i++){
    const newDiffs = {};
    
    for (d in diffs){
      // Swap
      let d1 = Number(d) + B[i] - A[i];
      if (diffs.hasOwnProperty(d1) && diffs[d1].length < diffs[d].length + 1)
        update(newDiffs, d1, diffs[d1]);
      else
        update(newDiffs, d1, diffs[d].concat(i+1));
        
      d1 = Number(d) + A[i] - B[i];
      if (diffs.hasOwnProperty(d1) && diffs[d1].length < diffs[d].length)
        update(newDiffs, d1, diffs[d1]);
      else
        update(newDiffs, d1, diffs[d]);
    }
    
    diffs = newDiffs;
  }

  console.log(JSON.stringify(diffs) + '\n\n');
  
  let best = Infinity;
  let idxs;

  for (let d in diffs){
    const _d = Math.abs(Number(d));
    if (_d < best){
      best = _d;
      idxs = diffs[d];
    }
  }

  return [best, idxs];
};

var A = [1, 1, 4, 4, 0, 6];
var B = [6, 3, 1, 1, 6, 1];

console.log(JSON.stringify(f(A, B)));

user_20347870

Here's a C++ implementation of mine based on Javascript answer of גלעד ברקן.

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;
}
user_67410530
Related