CODEWITHSUNDEEP
javascriptalgorithm
kilojoules
kilojoules

Reputation: 10083

Algorithm to find sum of summing pair idexes

I am working to create a function which, given a list of numbers and target number, returns the sum of the indexes of the list associated with numbers which can be paired with one other number in the list to create the target number. When possible, this sum should be minimized.

For example, f([0, 0, 0, 0, 1, 1], 1) should return 10 because there are two pairs of numbers which sum to one, and the lowest valued indexes of these pairs are (0,4) and (1,5), and 0+1+4+5=10.

f([1, 1, 1], 2) should yield 1 - the lowest value summing pairs indexes are (0,1) and 0+1 = 1

Here is my attempt so far. I don't understand why my algorithm doesn't work for the second case. My strategy is to search from lowest to highest index, ensuring that lower values indexes are logged first.

function pairwise(arr, arg) 
{
  // initiate log with all zeros
  var log = [];
  for (var i = 1; i <= arr.length; i++) 
  {
   log.push(0);
  }
  // look for summing pairs
  for (i = 0; i < arr.length; i++) 
  { 
    for (j = i; j < arr.length; j++) 
    { 
       // check if summing pair
      if(arr[i] + arr[j] == arg

        // also check if either number has been logged
        && log[i] == 0
        && log[j] == 0)
      {
        log[i] = 1;
        log[j] = 1;
      }
    }
  }

  // include only indexes with summing pairs in sum
  var summ = 0;
  for (var i = 1; i < arr.length; i++) 
  {
    summ = summ + log[i] * i;
  }  
  return summ;
}

pairwise([1, 1, 1], 2); // returns 3 not 1

Upvotes: 0

Views: 91

Answers (1)

Maurice Perry
Maurice Perry

Reputation: 32831

To avoid comparing an element with itself, you should use:

  for (i = 0; i < arr.length-1; i++) 
  { 
    for (j = i+1; j < arr.length; j++)

Upvotes: 2

Related Questions