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

Question

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.

Answer 1

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)));