Unique Permutations of Summing Pairs: Javascript Algorithm

Question

I have completed an inefficient, but a working algorithm to figure out which pair of numbers in an array (arr1) add up to the sum. I am facing these two problems:

(1) It is giving me "every" pair (e.g. 1+11 as well as 11+1 when the sum is 12),

AND

(2) I don't want it to add a number to itself (e.g. findArrSum([1, 3, 4, 8, 9, 11, 6, ], 12) I do not want it to return (6+6)). I can make this ignore 6 through my if statement, but in that case it will also ignore the solution (6+6 in this example findArrSum([1, 3, 4, 8, 9, 11, 6, 6], 12).

function findArrSum(arr1, sum) {   
  var i = 0;

  for (i in arr1) {
      arr1.map(function(num) {

       var answerSum = (num + arr1[i]);
       if (answerSum == sum && num != arr1[i]) {

                console.log(num +"+" +arr1[i] +"=" +sum);


                }
        });
    }
}
console.log('Enter an array and a sum that you want a pair to add to: ')

`arr1.map(function(num, b) {`, then `num != arr1[i]` becomes `(num != arr1[i] && i!=b)` — dandavis, Jan 28 '16 at 06:12
[Why is using “for…in” with array iteration such a bad idea?](http://stackoverflow.com/q/500504/1529630) — Oriol, Jan 28 '16 at 06:46
so I would switch it to for (i = 0; i < arr1.length-1; ++); ? — Matty, Jan 28 '16 at 06:49

score 2 · Answer 1 · answered Jan 28 '16 at 06:16

Both your issues can be solved by making small changes like

function findArrSum(arr1, sum) {   
  var i = 0;
  var usedSumArray = []; //new array introduced to store already done sums
  for (i in arr1) {
      arr1.map(function(num) {
       var thisSum = num +"+" +arr1[i]; //storing sum string
       if ( num != arr1[i] && usedSumArray.indexOf( thisSum ) == -1 ) //checking if the number is same or sum already done
       {
          usedSumArray.push( thisSum );
          var answerSum = (num + arr1[i]);
          if (answerSum == sum && num != arr1[i]) 
         {
            console.log(num +"+" +arr1[i] +"=" +sum);
         }
       }
     });
   }
}

Oriol · Accepted Answer · 2016-01-28T06:28:46.887

A naive algorithm would be

function findArrSum(arr, sum) {
  for(var i=0; i<arr.length; ++i)
    for(var j=i+1; j<arr.length; ++j)
      if(arr[i] + arr[j] === sum)
        console.log(arr[i] + ' + ' + arr[j] + ' = ' + sum);
}

But that costs n^2. We can do better by sorting first, and then using dichotomic searches

function dicSearch(arr, item, from, to) {
  if(from === to) return -1;
  var mid = Math.floor((from + to) / 2);
  if(arr[mid] > item) return dicSearch(arr, item, from, mid);
  if(arr[mid] < item) return dicSearch(arr, item, mid+1, to);
  return mid;
}
function findArrSum(arr, sum) {
  arr.sort(function(a,b) {
    return a-b;
  });
  for(var i=0; i<arr.length; ++i) {
    var j = dicSearch(arr, sum-arr[i], i+1, arr.length);
    if(j >= 0)
      console.log(arr[i] + ' + ' + arr[j] + ' = ' + sum);
  }
}

That should cost only n log n. You can even speed it up a bit by stopping iterating when your reach the minimum j found, instead of reaching arr.length.

But we can do it even faster by using a hash.

function findArrSum(arr, sum) {
  var hash = Object.create(null); // Also consider ES6 map
  for(var i=0; i<arr.length; ++i) {
    var j = hash[arr[i]];
    if(j != null)
      console.log(arr[i] + ' + ' + arr[j] + ' = ' + sum);
    hash[sum-arr[i]] = i;
  }
}

That only costs n on average.

Fixed problems and the overall inefficiencies. Didn't really know about using a hash for javascript. — Matty, Jan 28 '16 at 06:56

Unique Permutations of Summing Pairs: Javascript Algorithm

2 Answers2