How to pick elements from both arrays so that the difference between the sum is the minimum

user_10523471 0
Viewed 68

There are 2 arrays where the length of both arrays are the same.

array A = set of non-negative integers

array B = set of non-positive integers

I must either select A[i] or B[i] for each index i and want to know the minimum of abs(sum).

e.g

example 1

A = {1,2,3,4} , B = {-1,-2,-3,-4}

then the minimum of abs(sum) would be 0 by selecting 1, -2, -3 and 4. (-1, 2, 3, -4) also works.

example 2

A = {1,1,1,3} , B = {0,0,0,-3}

then the minimum of abs(sum) would be 0 by selecting 1,1,1 and -3.

I can only think of naive way of computing every possible combinations which takes exponential time. Could there be any better approach for this problem?

dynamic-programming arrays algorithm
1 Answers

This can be done in O(n * num_diffs) time complexity by imagining that the bucket of negatives is just another bucket of positives we are trying to get as close to the other as possible.

JavaScript code (a diff is the difference created when placing an item one of the buckets):

function f(A, B){
  let diffs = new Set();
  diffs.add(A[0]);
  diffs.add(-B[0]);
  
  for (let i=1; i<A.length; i++){
    let newDiffs = new Set();
    for (d of [...diffs]){
      newDiffs.add(d + A[i]);
      newDiffs.add(Math.abs(d + B[i]));
    }
    diffs = newDiffs;
  }
  console.log(`Diffs: ${ [...diffs] }`); 
  return Math.min(...diffs);
}

var ABs = [
  [[1, 2, 3, 4], [-1, -2, -3, -4]], // 0
  [[1, 1, 1, 3], [0, 0, 0, -3]] // 0
]

for (let [A, B] of ABs){
  console.log(`A: ${ A }`);
  console.log(`B: ${ B }`);
  console.log(`Result: ${ f(A, B) }`);
  console.log('');
}

user_20347870
Related