Given an array, count the pairs whose sums are multiples of 60

user_10908972 0
Viewed 3264

Given an array, how do you find the number of couples (two values) that add up to 60 or a value divisible by 60. Note: Must be faster than O(N^2).

Input: [10, 50, 30, 90] Output: 2 Reasoning: 10+50 = 60, 30 + 90 = 120 ( 120 is divisible by 60)

Input: [60,60,60] Output: 3 Reasoning: 60 + 60 = 120, 60 + 60 = 120, 60 + 60 = 120

The code I have below would run in O(N) time, but I do not know how to take care of the pairs that are equal to each other (ie if you have 2 30 values in the array that would add 1 to your counter, but if you have 3 30 values in the array that would add 3 to your counter). I figured I should create a combination function (ie 2C2 or 3C2), but that is a linear function and wouldn't that just make the function back to O(N^2)?

values(myList) {
    var obj = {};
    var count = 0;

    // loop through array and mod each value and insert it into a dictionary
    myList.forEach((elem, index) => {
        if (!obj.hasOwnProperty(elem % 60)) {
            obj[elem % 60] = 1;
        } else {
            obj[elem % 60]++;
        }
    });

    for (var keys in obj) {
        if (obj.hasOwnProperty(60 - keys)) {
            if (60 - keys == keys) {
                // take care of pairs
                // obj[keys] = x --> xC2
            } else {
                count += Math.min(obj[keys], obj[60 - keys]);
                delete obj[keys]
                delete obj[60 - keys];
            }
        }
    }
    return count;
}
big-o time-complexity algorithm javascript
4 Answers

There is no combination needed. It's simple math.

It's n * (n-1) / 2.

Let's say you have 4 items a,b,c,d.

Pairs would be:

  • (a,b)
  • (a,c)
  • (a,d)
  • (b,c)
  • (b,d)
  • (c,d)

For 4 items, we have 4 * 3 / 2 = 6.

#UPDATE:

Change 

count += Math.min(obj[keys], obj[60 - keys]);

to 

count += obj[keys] * obj[60 - keys];

Consider 2 keys- 12 and 48.

  • Key 12 has elements - 12,72,132
  • Key 48 has elements - 48,108

Technically, you are storing counts for them, which will be 3 and 2. If you observe, total no. of pairs we can make is 3 * 2 = 6 and not Math.min(3,2);

user_49648220

You can compute nC2 in O(1) time, because nC2 = n!/(n−2)!·2! = n·(n−1)·(n−2)!/(n−2)!·2! = n·(n−1)/2! = n·(n−1)/2.

That said, you might want to consider a different approach: instead of having a separate loop to compute count based on obj, you can add to count as you are building obj. That might be more intuitive, since it eliminates the need for special cases. (Up to you.)

Incidentally, your if (60 - keys == keys) test is not correct; that will detect the case where keys == 30, but not the case where keys == 0. (There may also be some other bugs you'll need to sort through.)

user_9789170

update: this solution is n^2, so this does not answer the original question.

let values = [60,10,20,50,40,30, 120, 60, 10];

let count = 0;

for (let i = 0; i < values.length; i++){
    for (let j = i+1; j < values.length; j++){
        let v = values[i] + values[j];
        if (v == 60 || !(v % 60)){
            count++;
        }
    }    
}

update 2:

To make it n + n*log(n), one could create a sorted tree with the mod values and then iterate through each of the mod value and look for 60-mod value values to find the number of pairs making up the difference. nodes can be optimised storing the number of repetitions as well. would that solve your problem?

user_6875710

If we count the pairs each element can make with the numbers seen so far, we can use simple addition rather than manage combinatorics or delicate edge cases.

function f(A, m){
  const rs = new Array(m+1).fill(0);
  for (let x of A){
    if (rs[(m - x % m) % m])
      rs[m] += rs[(m - x % m) % m];
    rs[x % m]++;
  }
  return rs[m];
}

console.log(f([10, 50, 30, 30], 60));
console.log(f([30, 10, 50, 30, 30], 60));
console.log(f([1, 5, 3, 3, 6, 24], 6));

(By the way, I'm not sure why you are making a differentiation between two numbers that add up to 60 and pairs that sum to a value divisible by 60 since the former is contained in the latter.)

user_20347870
Related