How can I return only the number of matching pair values in array?

Question

Say I found a box of loose shoes (all the same kind) at a garage sale, and I've created an array with each individual shoe listed by shoe size.

I want to display the number of paired values of shoe sizes in the array. For example, I have this array:

[10,10,10,10,20,20,20,30,50]

I would like to display 3 because we have 3 pairs of numbers:

10,10
10,10
20,20

And 3 remaining values that don't have a matching pair-value (20,30,50).

How can I do this?

function pairNumber(arr) {
  var sorted_arr = arr.sort();
  var i;
  var results = [];
  for (i = 0; i < sorted_arr.length; i++) {
    if (sorted_arr[i + 1] == sorted_arr[i]) {
      results.push(sorted_arr[i]);
    }

  }
  return results.length;
}
console.log(pairNumber([10, 10, 10, 10, 20, 20, 20, 30, 50]))

Do you understand why you get 5 instead of 3? If so, then you should be able to fix that. — Carsten S, Sep 08 '19 at 15:13
Yes I understand, I did fix it since yesterday. Do I have to fix it in the post as well? — Diasline, Sep 08 '19 at 15:41

Matt Aft · Accepted Answer · 2019-10-09T05:11:46.603

14

Here is another approach using a Set:

function pairNumbers(arr) {
  let count = 0;
  const set = new Set();

  for (let i = 0; i < arr.length; i++) {
    if (set.delete(arr[i])) {
      count++;
    } else {
      set.add(arr[i])
    }
  }

  return count;
}
console.log(pairNumbers([10, 10, 10, 10, 20, 20, 20, 30, 50])) // 3

edited Oct 09 '19 at 05:11

answered Sep 07 '19 at 21:52

Matt Aft

8,742
3
24
37

You can simply omit the `set.has` part as `set.delete` returns what `set.has` would have returned: `if(set.delete(arr[i])){...}else{...}` – FZs Oct 08 '19 at 14:25
@FZs True, that would be an optimization – Matt Aft Oct 09 '19 at 05:11

score 8 · Answer 2 · answered Sep 07 '19 at 21:44

8

I'd reduce into an object, counting up the number of occurrences of each number. Then reduce again on the Object.values of the object to count up the number of pairs, adding Math.floor(count / 2) to the accumulator on each iteration:

function pairNumber(arr) {
  const itemCounts = arr.reduce((a, item) => {
    a[item] = (a[item] || 0) + 1;
    return a;
  }, {});
  return Object.values(itemCounts)
    .reduce((pairsSoFar, count) => pairsSoFar + Math.floor(count / 2), 0);
}
console.log(pairNumber([10, 10, 10, 10, 20, 20, 20, 30, 50]))

Probably better to avoid .sort if possible - that increases the computational complexity from O(n) (minimum) to O(n log n).

answered Sep 07 '19 at 21:44

CertainPerformance

356,069
52
309
320

I wonder if building `itemCounts` doesn't add the same `O(nlogn)` back? How do objects work under the hood? Hashtables? Balanced trees? – Vilx- Sep 07 '19 at 21:49
For any remotely sane implementation, it'll be `O(1)`, luckily: https://stackoverflow.com/questions/7700987/performance-of-key-lookup-in-javascript-object . If using an object causes an issue, could use a Map instead – CertainPerformance Sep 07 '19 at 21:50

EugenSunic · Answer 3 · 2019-09-08T12:39:34.507

If I understood the question well then this can be simplified even further by relying on sort initially...

Increment i to the next position after finding the pair and let the for loop increment it once again.

 function pairNumber(arr) {
    const sorted_arr = [...arr].sort(); // disallowing array mutation
    let cnt = 0;
    for (let i = 0; i < sorted_arr.length; i++) {
      if (sorted_arr[i + 1] === sorted_arr[i]) {
        cnt++;
        i = i + 1;
      }

    }
    return cnt;
  }
  console.log(pairNumber([10, 10, 10, 10, 10, 20, 20, 20, 20, 30, 30, 50]))
  // 5 --> 2 pairs of 10, 2 pairs of 20, 1 pair of 30
  console.log(pairNumbers([10, 10, 10, 10, 20, 20, 20, 30, 50])) 
  // 3 --> 2 pairs of 10 one pair of 20

I believe `sort` will mutate the original array, so a side-effect would be that the array being passed in will be sorted after calling this function. — Matt Aft, Sep 07 '19 at 23:06

score 0 · Answer 4 · edited Oct 08 '19 at 05:28

Many thanks to all guys that help me understand more how to solve this issue. After studying the answers in the post I come up with my own solution.

Thanks to you I understand I should increment i at the end of if to prevent a repetitive comparison.

function pairNumbers(arr) {
  const sorted_arr = arr.sort();
  const results = [];
  for (let i = 0; i < sorted_arr.length; i++) {
    if (sorted_arr[i] == sorted_arr[i + 1]) {
      results.push(sorted_arr[i]);
      i = i + 1; 
    }
  }
  return results.length;
}
console.log(pairNumbers([10, 10, 10, 10, 20, 20, 20, 30, 50])) // 3

How can I return only the number of matching pair values in array?

4 Answers4