Algorithm Pairwise

Algorithm Pairwise
0

#1

:triangular_flag_on_post: Remember to use Read-Search-Ask if you get stuck. Try to pair program :busts_in_silhouette: and write your own code :pencil:

:checkered_flag: Problem Explanation:

The program should look for pairs of numbers in the array whose sum equal the second argument arg. Then instead of adding those numbers up, their indices are to be added.

Remember that arrays start at index 0 and go from there so from [1,4,2,3,0,5] if we switch to their indices it would be [0,1,2,3,4,5]. Then, we add indices 1 + 2 + 3 + 5 and we get 11. That is what we need to return.

Relevant Links

:speech_balloon: Hint: 1

Remember to return the smaller sum if multiple are possible. This means ([1,1,1], 1) should use 0 + 1 instead of 0 + 1 & 1 + 1.

try to solve the problem now

:speech_balloon: Hint: 2

Try using an array of indices to track whether an index has been used or not.

try to solve the problem now

:speech_balloon: Hint: 3

It is easy to confuse indices as being numbers, but since you will be interacting with them, make sure to work with them as integers to prevent the code from behaving erratically.

try to solve the problem now

Spoiler Alert!

687474703a2f2f7777772e796f75726472756d2e636f6d2f796f75726472756d2f696d616765732f323030372f31302f31302f7265645f7761726e696e675f7369676e5f322e676966.gif

Solution ahead!

:beginner: Basic Code Solution:

function pairwise(arr, arg) {
 // Set sum of indices to zero
 var sum = 0;
 // make a local copy of the arguments object so we don't modify it directly
 var pairArr = arr.slice();
 // looping from first element
 for(i = 0; i < pairArr.length; i++) {
   //Looping from second element by setting first element  constant
   for(j = i + 1; j < pairArr.length; j++) {
     // Check whether the sum is equal to arg
     if(pairArr[i] + pairArr[j] == arg) {
       //Add the indices
       sum += i + j;
       //Set the indices to NaN so that they can't be used in next iteration
       pairArr[i] = pairArr[j] = NaN;
     }
   }
 }
 return sum;
}

// test here
pairwise([1,4,2,3,0,5], 7);

:rocket: Run Code

Code Explanation:

  • The variable sum holds the sum of indices.
  • The outer for loop starts from the first element of arr.
  • The inner for loop starts from the second element of arr.
  • If the sum of an element and the element succeeding it is equal to arg:
    • The sum of the indices of these elements is added to sum.
    • These elements are set to NaN so that they’re not used in the next iteration.
  • After the loops are completed, the sum is returned.

Relevant Links

:sunflower: Intermediate Code Solution:

function pairwise(arr, arg) {
  // Create empty array to keep the arrays we will add.
  var index = [];

  // Loop to check the first number.
  for (var a in arr) {
    // temporal first number.
    var temp = arr[a];

    // Second loop to check against the first number.
    for (var i = 1; i < arr.length; i++) {
      // temporal second number.
      var temp2 = arr[i];

      // Key element, this check to make sure that the numbers add to arg
      // also that the second index is greater than the first, and that neither
      // of those indices are already on the array.
      if (temp + temp2 === arg && i > a && index.indexOf(+a) === -1 && index.indexOf(+i) === -1) {
        // if true then add both indices as integers then stop checking to avoid repeats.
        index.push(+a, +i);
        break;
      }
    }
  }

  // After the two loops are done, check if index is empty to return 0
  // or if it is not, then use Array.reduce(callbackFunc) to return the sum
  // of the numbers.
  if (index.length >= 1) {
    var addAll = function(a, b) {
      return a + b;
    };

    return index.reduce(addAll);
  } else
      return 0;
}

// test here
pairwise([1,4,2,3,0,5], 7);

:rocket: Run Code

Code Explanation:

  • First, an empty array index is created to store the indices that will be added.
  • The outer loop gets the first number.
  • The inner loop gets the second number.
  • The following has to be made sure:
    • The two numbers add to arg that was passed as a parameter to the function.
    • The index from the second loop is greater than the one from the first loop. This avoids adding wrong indices.
    • The indices are not already part of the index array.
  • If all the conditions are true, the two indices are added as integers using + or parseInt(). The inner loop is hence stopped; everything else would be redundant.
  • After all the loops are over, it is checked if index is empty:
    • If it is empty, then 0 is returned.
    • Otherwise, the sum of all the integers in it is returned. This is done using the reduce() method.

Relevant Links

:rotating_light: Advanced Code Solution:

function pairwise(arr, arg) {
  // search array for elements that when paired, equal the second argument, then sum their indices
  // make a local copy of the arguments object so we don't modify it directly
  var pairArr = arr.slice();
  return pairArr.reduce( function (a,b,index){ // use native reduce to collect running total of summed indices
      var search = arg - b; // get difference of current item so we know what value will sum to arg

      // check if search value in rest of the array, but also make sure it doesn't match current search index
      if ( pairArr.indexOf(search) != -1 && pairArr.indexOf(search) != index ){ 
         var total = index + pairArr.indexOf(search);  // if found, add to the runnning total
         pairArr.splice(index,1,NaN); // remove current index from the array
         pairArr.splice(pairArr.indexOf(search),1,NaN); // remove the other matched element from the array
         return a + total; //return the running total back to reduce for next item
      }
      return a; // simply return previous total if no operations needed
  },0);
}
// test here
pairwise([1,4,2,3,0,5], 7);

:rocket: Run Code

Code Explanation:

See comments in code
This code takes advantage of the fact that the native Array.prototype.indexOf() method will return the lowest index of the value it finds, a requirement of the challenge. Given that you start with the first item in the array (automatically the lowest of it’s value), you’re guaranteed to always find the lowest pairs, before removing them from the search space.

Relevant Links

:clipboard: NOTES FOR CONTRIBUTIONS:

  • :warning: DO NOT add solutions that are similar to any existing solutions. If you think it is similar but better, then try to merge (or replace) the existing similar solution.
  • Add an explanation of your solution.
  • Categorize the solution in one of the following categories — Basic, Intermediate and Advanced. :traffic_light:
  • Please add your username only if you have added any relevant main contents. (:warning: DO NOT remove any existing usernames)

See :point_right: Wiki Challenge Solution Template for reference.


#17

By @P1xt

If there is, I haven’t found a comprehensive reference. Personally, I like seeing “proof” so I tend to just code up a quick node script with a function for each of the various ways I might consider solving a problem (once I’ve winnowed down the possible solutions to the ones that, on the face, seem the least complex - logarithmic or linear time as opposed to quadratic or polynomial) and use the benchmark npm module to give me cold hard data about which of the remaining solutions are the most efficient. Then, I weight differences in efficiency against ease of maintenance and code readability.

For instance, I just ran benchmark on the three solutions in the wiki and the refactor I did on the advanced solution, and my prediction proved true - the basic solution is actually the fastest of the four, which makes sense because for loops are wicked fast, and array methods are slower. The results:

pairwiseBasic x 2,109,026 ops/sec ±0.98% (86 runs sampled)
pairwiseIntermediate x 141,785 ops/sec ±7.66% (75 runs sampled)
pairwiseAdvanced x 368,720 ops/sec ±1.43% (80 runs sampled)
pairwiseRefactored x 1,041,321 ops/sec ±1.82% (77 runs sampled)

Now, I’m going to see if there’s any way to boost the Basic algorithm to make it even faster using some of the tactics from the advanced algorithm.

Edit -
Actually, once I profiled a couple different versions, the fastest I could come up with was:

function pairwiseRefactored2(arr, arg) {
 var sum = 0, pairArr = arr.slice(), len = pairArr.length, i, j;

 for(i = 0; i < len; i++) {
   for(j = i + 1; j < len; j++) {
     if(pairArr[i] + pairArr[j] == arg) {
       sum += i + j;
       //Set the indices to NaN so that they can't be used in next iteration
       pairArr[i] = pairArr[j] = NaN;
       break;
     }
   }
 }
 return sum;
}

Which adds only a couple minor efficiencies over the basic solution. First, it only calculates the length of the array once and then uses that variable instead of using pairArr.length over and over for each repeat of each loop. Second, it adds a break within the if statement, because if that index was matched and set to NaN, there’s no reason to check it against the rest of the j’s.

I tried using indexOf in place of the second for loop, but it was only modestly faster than my refactor of the advanced solution and still only half(ish) the speed of the basic.

For anyone interested in the giant wall o text:

Benchmark Results and Script

Benchmark Results

pairwiseBasic x 2,181,940 ops/sec ±1.12% (75 runs sampled)
pairwiseIntermediate x 164,147 ops/sec ±0.86% (82 runs sampled)
pairwiseAdvanced x 367,085 ops/sec ±1.75% (75 runs sampled)
pairwiseRefactored x 1,070,409 ops/sec ±1.56% (82 runs sampled)
pairwiseRefactored2 x 2,516,796 ops/sec ±0.95% (79 runs sampled)
pairwiseRefactored3 x 1,131,890 ops/sec ±0.96% (82 runs sampled)
Fastest is pairwiseRefactored2

Benchmark Script

var Benchmark = require('benchmark');
var suite = new Benchmark.Suite;

function pairwiseBasic(arr, arg) {
 // Set sum of indices to zero
 var sum = 0;
 // make a local copy of the arguments object so we don't modify it directly
 var pairArr = arr.slice();
 // looping from first element
 for(i = 0; i < pairArr.length; i++) {
   //Looping from second element by setting first element  constant
   for(j = i + 1; j < pairArr.length; j++) {
     // Check whether the sum is equal to arg
     if(pairArr[i] + pairArr[j] == arg) {
       //Add the indices
       sum += i + j;
       //Set the indices to NaN so that they can't be used in next iteration
       pairArr[i] = pairArr[j] = NaN;
     }
   }
 }
 return sum;
}

function pairwiseIntermediate(arr, arg) {
  // Create empty array to keep the arrays we will add.
  var index = [];

  // Loop to check the first number.
  for (var a in arr) {
    // temporal first number.
    var temp = arr[a];

    // Second loop to check against the first number.
    for (var i = 1; i < arr.length; i++) {
      // temporal second number.
      var temp2 = arr[i];

      // Key element, this check to make sure that the numbers add to arg
      // also that the second index is greater than the first, and that neither
      // of those indices are already on the array.
      if (temp + temp2 === arg && i > a && index.indexOf(+a) === -1 && index.indexOf(+i) === -1) {
        // if true then add both indices as integers then stop checking to avoid repeats.
        index.push(+a, +i);
        break;
      }
    }
  }

  // After the two loops are done, check if index is empty to return 0
  // or if it is not, then use Array.reduce(callbackFunc) to return the sum
  // of the numbers.
  if (index.length >= 1) {
    var addAll = function(a, b) {
      return a + b;
    };

    return index.reduce(addAll);
  } else
      return 0;
}

function pairwiseAdvanced(arr, arg) {
  // search array for elements that when paired, equal the second argument, then sum their indices
  // make a local copy of the arguments object so we don't modify it directly
  var pairArr = arr.slice();
  return pairArr.reduce( function (a,b,index){ // use native reduce to collect running total of summed indices
      var search = arg - b; // get difference of current item so we know what value will sum to arg

      // check if search value in rest of the array, but also make sure it doesn't match current search index
  if ( pairArr.indexOf(search) != -1 && pairArr.indexOf(search) != index ){ 
     var total = index + pairArr.indexOf(search);  // if found, add to the runnning total
     pairArr.splice(index,1,NaN); // remove current index from the array
     pairArr.splice(pairArr.indexOf(search),1,NaN); // remove the other matched element from the array
     return a + total; //return the running total back to reduce for next item
  }
  return a; // simply return previous total if no operations needed
  },0);
}

function pairwiseRefactored(arr, arg) {
  var pairArr = arr.slice();
  return pairArr.reduce( function (a,b,index){ 

    // find a match that will sum to correct total
    var searchIdx = pairArr.indexOf(arg -b);

    // if match found and it's not this same index
    if ( searchIdx != -1 && searchIdx != index ){ 
        // mark indexes used and add into running total
        pairArr[index] = pairArr[searchIdx] = NaN;
        return a + index + searchIdx; 
    }

    // else skip this one and move to the next
    return a; 
  },0);
}
function pairwiseRefactored2(arr, arg) {
 var sum = 0, pairArr = arr.slice(), len = pairArr.length, i, j;

 for(i = 0; i < len; i++) {
   for(j = i + 1; j < len; j++) {
     if(pairArr[i] + pairArr[j] == arg) {
       sum += i + j;
       //Set the indices to NaN so that they can't be used in next iteration
       pairArr[i] = pairArr[j] = NaN;
       break;
     }
   }
 }
 return sum;
}
function pairwiseRefactored3(arr, arg) {
 var sum = 0, pairArr = arr.slice(), len = pairArr.length, i, j;

 for(i = 0; i < len; i++) {
    var searchIdx = pairArr.indexOf(arg - pairArr[i]);

    // if match found and it's not this same index
    if ( searchIdx != -1 && searchIdx != i ){ 
        // mark indexes used and add into running total
        pairArr[i] = pairArr[searchIdx] = NaN;
        sum += i + searchIdx; 
    }
 }
 return sum;
}
// add tests
suite
.add('pairwiseBasic', function() {
    pairwiseBasic([1,4,2,3,0,5], 7);
})
.add('pairwiseIntermediate', function() {
    pairwiseIntermediate([1,4,2,3,0,5], 7);
})
.add('pairwiseAdvanced', function() {
    pairwiseAdvanced([1,4,2,3,0,5], 7);
})
.add('pairwiseRefactored', function() {
    pairwiseRefactored([1,4,2,3,0,5], 7);
})
.add('pairwiseRefactored2', function() {
    pairwiseRefactored2([1,4,2,3,0,5], 7);
})
.add('pairwiseRefactored3', function() {
    pairwiseRefactored3([1,4,2,3,0,5], 7);
})
// add listeners
.on('cycle', function(event) {
   console.log(String(event.target));
})
.on('complete', function() {
   console.log('Fastest is ' + this.filter('fastest').map('name'));
})
// run async
.run({ 'async': true });



Video + Statistics of Two Chunky Monkey Codes Performance
#18

#19

#20

…Another solution with REDUCE… No code explanation needed … i hope …

function pairwise(arr, arg) {
  var indexSum = 0,
      len = arr.length,
      checkValue = NaN;
  if (len === 0) return indexSum;
  arr.reduce(function(acc,curr,index,array){
    for (var i = index; i < len; i++){
      //check for the same array's value
      if (checkValue === array[i]) {
        array[i] = NaN;
      };
      if (acc + array[i] === arg) {
        indexSum += (index-1)+i;
        checkValue = acc;
        array[i] = NaN;
        break; 
      };
    };
    acc = curr;
    return acc;
  });
  return indexSum;
}

pairwise([1,4,2,3,0,5], 7);

#21

I would like to add another basic yet fast solution. It basically selects an element from the array, add it to the other elements in the array, if the sum is equal to the argument then it records the sum of the indices and deletes the pair from the array, hence replacing their value with “undefined”.

function pairwise(arr, arg) {
    var result = 0;
  for(var x = 0 ; x <arr.length; x++){
    for(var y = 0; y <arr.length; y++){
      if(x === y){
        break;
     }
      if(arr[x] + arr[y] === arg){
        result += x + y;
        delete arr[x];
        delete arr[y];
      } 
    }
  }
  return result;
}

#22

you all can decide if this is basic, intermediate or advanced. I spent a long long time on this challenge and created this beastly code that I couldn’t even follow myself. took a break and came up with this extremely simple and, in my opinion, easy to follow solution.


function pairwise(arr, arg) {

  if (arr.length===0) { // arrays with no elements should not pass further through the code
    sum=0;
    return sum;
  }
  var indexArray=[];
  var first;
  // the for loop takes the index of variable first (two numbers a and b, first is 'a') and then
  // uses the arr.indexOf function to find the first index with the 'b' value that adds up to 
  // arg.
  // if the arr.indexOf returns -1, that means there is no element in the array with the 'b' value.
  // The last part of the if statement below makes sure that the 'a' value and the 'b' value
  // do not come from the same index in the array.
  for (i=0; i<arr.length; i++) {
    first=arr[i];
    var filtered= arr.indexOf(arg-first);
    if (filtered !==-1 && filtered !==i){
      // push the index pair who's elements add up to 'arg' to indexArray
      indexArray.push(i, filtered);
      // change the values in arr to a fictictious number so that they will never successfully
      // add up with another element to equal 'arg'
      arr.splice(i,1, -10);
      arr.splice(filtered,1,-10);
    }
  }
  // now sum the elements of indexArray.  Remember the elements of indexArray are actually
  // the indicies of 'arr'.
  var sum=indexArray.reduce(sumIt,0);
  function sumIt(a, b) {
    return a+b;
  }
  return sum;
}


#23

For some reason, the first thing that comes to my mind when thinking of a replacement of a for loop is the Array.prototype.forEach method, so this working solution may be added to the pile:

// Credit goes to the advanced solution already provided on the FreeCodeCamp forum
function pairwise(arr, arg) {
var result=0;

arr.forEach(function(element,indexOfElement){
// It’s a good idea to always have a variable containing the search value before proceeding
var searchValue=arg-element;

if (arr.indexOf(searchValue)>-1 && arr.indexOf(searchValue)!=indexOfElement){
  result+=indexOfElement+arr.indexOf(searchValue);
  delete arr[indexOfElement];
  delete arr[arr.indexOf(searchValue)];
}

});

return result;
}


#24
function pairwise(arr, arg) {
  var noMut = Array.from(arr);                    //copy arr
  var indices = 0;                                //sum of indices
  var index;
  for(var i = 0; i < noMut.length -1; i++) {      //last element have not pair
    index = noMut.indexOf(arg - noMut[i], i + 1); //search index
    if(index !== -1) {
      indices += i + index;
      noMut[i] = noMut[index] = NaN;
    }  
  }
  return indices;
}

#25
function pairwise(arr, arg) {
  return arr.reduce(function(sum,cur,i,ar){
        for(var j=i+1;j<ar.length;j++){
          if(cur+ ar[j]=== arg){
             sum+=i+j;
            ar[j]=' ';
             break;
          }
      }

return sum;

},0);
}


#26

Here’s another solution using reduce. No deleting or marking necessary.

 function pairwise(arr, arg) {
  var pairs = [];

  for (var i = 0; i < arr.length; i++) {
    for (var k = 0; k < arr.length; k++) {
      if (arr[i] + arr[k] == arg) {
        if (pairs.indexOf(i) < 0 && pairs.indexOf(k) < 0 && i != k) {
         pairs.push(i, k);
      }
    }
  }
}
if (pairs.length > 1) {
  return pairs.reduce(function(acc, val) {
    return acc + val;
  });
} else {
  return 0;
}
}

#27

Here’s a simple solution to the problem.

function pairwise(arr, arg) {
  if (arr.length == 0){ return 0;};
  
  return arr.reduce(function(acc,val,idx){
               
                 for (var x = idx; x < arr.length; x++){ //Goes through array starting at current value used in reduce
                   
                   if ((arr[x+1] + arr[idx]) === arg) //checks if current value and next spot in array equal the argument 
                   {
                     if(!acc.includes(idx) && !acc.includes(x+1)) // checks if either of the indices are already stored. 
                                                                 //If so, it wont add them again- ensuring the smallest ones are saved
                     {
                       acc.push(x+1,idx);//adds each index singularly, to make it easy to sum up with reduce later on.
                     }
                   }
                 }
                 
                return acc;

             },[]).reduce(function(acc, val){return acc +val;});//sums up the indices to finish up the problem.
 
}  

As I looked at various solutions, now that I’m done that is, I realize it could’ve been easier to just remove or mark the indices that were used instead of an IF statement. :stuck_out_tongue:


#28

The ‘Relevant Links’ don’t appear to be linked to anything.


#29

I used an object to store the indexes of the values which summed to the arg value instead of using indexOf or includes. The latter two still have to traverse the array, where the lookup on the object is only O[1]. Below is my original for loop version and then a functional version:

function pairwise(arr, arg) {
  let sum = 0;
  for (let used = {}, i=0; i<arr.length;i++) {
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[i] + arr[j] === arg && !used[i] && !used[j]) {
        used[i]=used[j] = true;
        sum += i+j;
      }
    }
  }
  return sum;
}

// functional solution;
function pairwise(arr, arg) {
  let used = {};
  return arr.reduce((sum,val,i,origArr) => origArr.reduce((sum2,val2,j) => {
    if (i !== j && val + val2 === arg && !used[i] && !used[j]) {
      used[i] = used[j] = true;
      sum2 += i+j;
    }
    return sum2;
  },sum),0);
}

#30

did it this way

function pairwise(arr, arg) {
var newArr = [];
var sum = 0;
function checkIsThere (i,j) {
var place = 0;
for (x = 0; x < newArr.length;x++) {
if (i===newArr[x] || j ===newArr[x]) {
return false;
}

}
return true;

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

  if (arg === arr[i] + arr[j] && checkIsThere(i,j)) {
    newArr.push(i);
    newArr.push(j);
    sum+= i;
    sum+= j;
  }
}

}
return sum;
}


#31

Got two short solutions, using .reduce (and one with .map as well). First attempt:

const pairwise = (arr, arg) => arr.map((e,i,a) => 
    a.indexOf(arg-e,i+1) > 0 || e === true ? a[a.indexOf(arg-e)] = true : false)
      .reduce((a,b,i)=> b ? a+=i : a,0);

Second attempt, without .map:

const pairwise = (arr, arg) => arr.reduce((p,c,i,a) => {
  let idx = a.indexOf(arg-c, i+1);
  return idx > 0 ? (c = a[idx] = NaN, p + i + idx) : p;
},0);

I wonder if I could compress it more, but it is 1.30 am and I need sleep.


#32

After reading some of these solutions, I’m worried that mine only works as far as the basic tests on the fcc map, but might not actually fulfill the specifications (for example the lowest combination of sums). My brain can’t stretch enough yet to figure out where this breaks down. Any thoughts/advice is appreciated.

function pairwise(arr, arg) {
  var sum=0;
  for (i=0;i<arr.length;i++){
    if (arr.indexOf(arg - arr[i]) !== -1 && arr.indexOf(arg - arr[i]) !== i){
      sum+= i + arr.indexOf(arg - arr[i]);
      arr[arr.indexOf(arg - arr[i])] = NaN;
      arr[i] = NaN;
    }
  }
  return sum;
}

#33

I’m struggling to figure out why pairwise([0, 0, 0, 0, 1, 1], 1) should return 10. It’s not making a lot of sense to me. It seems like the value should be 4?

Why does the test say it should equal 10?

Also, doesn’t the highest available pair of indexes total 9?

I must be missing something. Or is this a bug in the tests?


#34

The output should equal the sum of the indices whose values are summed to equal the second argument.

I.E., in the example you’re using, the first 0 is added to the first 1 in order to get the second argument, 1. Their indices are 0 and 4, 0 + 4 = 4

…then, the second 0 and the second 1 are similarly summed; their indices are 1 and 5, 1 + 5 = 6.

So, 0 + 4 + 1 + 5 = 10


#35

oh, I’ve got it! Ok so I definitely misunderstood the instructions. I was too liberal with my exclusions, I thought every single instance of a duplicated pair would be discarded, but I understand now how I was wrong.

Thank you for pointing this out for me! :slight_smile: