Torean Torean - 5 months ago 35
Javascript Question

Find the smallest sum of all indexes of unique number pairs summing to a given number

I want to loop through an array and then add each value to each other (except itself + itself) and if the sum of the two values that were looped through equals the second argument in my function, and the pair of values hasn't been encountered before, then remember their indices and, at the end, return the full sum of all remembered indices.




In other words, the problem statement is: given an array A of integers and a second value s that is a desired sum, find all pairs of values from array A at indexes i, j such that i < j and A[i] + A[j] = s, and return the sum of all indexes of these pairs, with the following restriction:


  • don't reuse value pairs, i.e. if two index pairs i, j and k, l satisfying the above conditions are found and if A[i] == A[k] and A[j] == A[l] or A[i] == A[l] and A[j] == A[k], then ignore the pair with the higher index sum.






Example

For example,
functionName([1, 4, 2, 3, 0, 5], 7)
should return 11 because values 4, 2, 3 and 5 can be paired with each other to equal 7 and the 11 comes from adding the indices of them to get to 11 where:

4 + 3 = 7
5 + 2 = 7

4 [index: 1]
2 [index: 2]
3 [index: 3]
5 [index: 5]

1 + 2 + 3 + 5 = 11





Example #2

functionName([1, 3, 2, 4], 4)
would only equal 1, because only the first two elements can be paired to equal 4, and the first element has an index of 0 and the second 1

1 + 3 = 4

1 [index: 0]
3 [index: 1]

0 + 1 = 1





This is what I have so far:

function functionName(arr, arg) {
var newArr = [];
for(var i = 0; i < arr.length; i++){
for(var j = i + 1; j < arr.length; j++) {
if((arr[i] + arr[j]) === arg ) {
newArr.push(i , j);
}
}
}

if(newArr.length === 0) {
return console.log(0);
}
return console.log(newArr.reduce(function(a,b){return a + b}));
}

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





The problem I have is that it all works but I have the issue that once it finds a pair that equals the second argument, then it's not supposed to use the same value pairs again but mine does, e.g.:

if the array is
[1,1,1]
and the second argument is
2
, the loop will go through and find the answer but it continues to search after it finds the sum and I only want it to use the pair
[1, 1]
once, so if it finds a pair like this at indexes
[0, 1]
then it should not include any other pair that contains the value
1
.




I was thinking that i could remove the rest of the values that are the same if more than 2 are found using filter leaving me with only 2 of the same value if there is in an array thus not having to worry about the loop finding a 1 + 1 twice but is this the best way to go about doing it?

I'm still new to this but looking forward to your comments

PS I'm planning on doing this using pure JavaScript and no libraries

Link to a JS fiddle that might make things easier to see what I have.
https://jsfiddle.net/ToreanJoel/xmumv3qt/

Answer

This is more complicated than it initially looks. In fact, making a loop inside a loop causes the algorithm to have quadratic time complexity with regard to the size of the array. In other words, for large arrays of numbers, it will take a very long time to complete.

Another way to handle this problem is to notice that you actually have to use each unique value in the array only once (or twice, if s is even and you have two s/2 values somewhere in the array). Otherwise, you would have non-unique pairs. This works because if you need pairs of numbers x and y such that x + y = s, if you know x, then y is determined -- it must be equal s - x.

So you can actually solve the problem in linear time complexity (to be fair, it's sometimes n*log(n) if all values in A are unique, because we have to sort them once).

The steps of the algorithm are as follows:

  1. Make a map whose keys are values in array A, and values are sorted lists of indexes these values appear at in A.
  2. Move through all unique values in A (you collected them when you solved step 1) in ascending order. For each such value:
    1. Assume it's the lower value of the searched pair of values.
    2. Calculate the higher value (it's equal to s - lower)
    3. Check if the higher value also existed in A (you're doing it in constant time thanks to the map created in step 1).
    4. If it does, add the lowest indexes of both the lower and the higher value to the result.
  3. Return the result.

Here's the full code:

function findSumOfUniquePairs(numbers, sum) {

  // First, make a map from values to lists of indexes with this value:
  var indexesByValue = {},
      values = [];
  numbers.forEach(function (value, index) {
    var indexes = indexesByValue[value];
    if (!indexes) {
      indexes = indexesByValue[value] = [];
      values.push(value);
    }
    indexes.push(index);
  });

  values.sort();

  var result = 0;

  for (var i = 0, maxI = values.length; i < maxI; ++i) {
    var lowerValue = values[i],
        higherValue = sum - lowerValue;
    if (lowerValue > higherValue) {
      // We don't have to check symmetrical situations, so let's quit early:
      break;
    }
    var lowerValueIndexes = indexesByValue[lowerValue];
    if (lowerValue === higherValue) {
      if (lowerValueIndexes.length >= 2) {
        result += lowerValueIndexes[0] + lowerValueIndexes[1];
      }
    } else {
      var higherValueIndexes = indexesByValue[higherValue];
      if (higherValueIndexes) {
        result += lowerValueIndexes[0] + higherValueIndexes[0];
      }
    }
  }

  return result;
}

document.write(findSumOfUniquePairs([1, 4, 2, 3, 0, 5], 7) + '<br>'); // 11;
document.write(findSumOfUniquePairs([1, 3, 2, 4], 4) + '<br>'); // 1
document.write(findSumOfUniquePairs([1, 1, 1], 2) + '<br>'); // 1
document.write(findSumOfUniquePairs([1, 1, 1, 1], 2) + '<br>'); // 1
document.write(findSumOfUniquePairs([1, 2, 3, 1, 2, 3, 1], 4) + '<br>'); // 7
document.write(findSumOfUniquePairs([5, 5, 1, 1, 1], 6) + '<br>'); // 2
document.write(findSumOfUniquePairs([0, 5, 0, 5, 1, 1, 1], 6) + '<br>'); // 5