Storing index - value pairs in a map then check with an array-CodePudding

I have two arrays: data and usedIndexes. First, I need to find all dividable (to another number in the array) numbers and store them with their indexes (let's say in myMap) and then somehow go through the second array "usedIndexes" and find dividable pairs that one of their index number is in usedIndexes array.

For example, given arrays: data: [8, 3, 5, 2, 7, 9, 50]
usedIndexes = [0, 1, 6]

const myMap = {}

  for (let i = 0; i < arr.length; i  ) {
    for(let y = i   1; y < arr.length; y  ) {
      if(arr[i] % arr[y] === 0 || arr[y] % arr[i] === 0 ) {
        if(!myMap[i]) {
           myMap[i] = arr[i]
         }

          if(!myMap[y]) {
             myMap[y] = arr[y];
          }
        }
     }
  }

So this will give me something like (index - value pair), myMap:

{
0: 8,
3: 2,
1: 3,
5: 9,
2: 5,
6: 50
3: 2,
6: 50
}

So actual dividable pairs like:
8 - 2
3 - 9
5 - 50
2 - 50

Quite frankly, I am not sure maybe map/object is not the best data structure to hold these values but I couldn't think something else.

Now, how can I loop through the usedIndexes array and find key-value pairs which at least one of the keys has in usedIndexes. Please read the comment in code sample below.

for (let i = 0; i < usedIndexes.length; i  ){
 // e.g. usedIndexes first element is 0 and myMap has 0:8 
 // but what I need to return 0:8 AND 3:2 because dividable pair is 8 - 2.
}

CodePudding user response：

Don't store the divisor value in the map, store its index:

const myMap = {};
for (let i = 0; i < arr.length; i  ) {
  for (let j = 0; j < arr.length; j  ) {
    if (i != j && arr[i] % arr[j] === 0) {
      myMap[i] = j;
      myMap[j] = i;
    }
  }
}

Then it's only a matter of going through usedIndexes to find those that appear as part of a pair in the map:

const result = [];
for (const index of usedIndexes) {
  if (index in myMap) {
    const other = myMap[index];
    result.push([{index, value: arr[index]}, {index: other, value: arr[other]}]);
  }
}
console.log(result);

However, this will not find all possible pair where one value divides the other and one value is referenced by a usedIndex. This is due to myMap storing only a single pair for each index, even when an index would be included in multiple pairs. (For simplicity I didn't bother to check whether the assignment would override an other value in the first snippet, it only changes whether the first or last combination would be found, it doesn't solve the problem).

To alleviate this problem, we should just get rid of the myMap and fill the result right inside the nested loop:

const result = [];
for (let i = 0; i < arr.length; i  ) {
  for (let j = 0; j < arr.length; j  ) {
    if (i != j && arr[i] % arr[j] === 0) {
      if (usedIndexes.includes(i) || usedIndexes.includes(j)) {
        result.push([{index: i, value: arr[i]}, {index: j, value: arr[j]}]);
      }
    }
  }
}
console.log(result);

The only problem with this solution is its inefficiency - usedIndexes.includes does iterate the usedIndexes array every time. You could alleviate that by creating a Set of indices then use .has() inside the loop, but we can actually do better: just don't iterate those indices in the first place!

const result = [];
for (const i of usedIndexes) {
  for (let j = 0; j < arr.length; j  ) {
    if (i != j) {
      const [a, b] = arr[i] > arr[j] ? [i, j] : [j, i];
      if (arr[a] % arr[b] === 0) {
        result.push([{index: a, value: arr[a]}, {index: b, value: arr[b]}]);
      }
    }
  }
}
console.log(result);