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

Question

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;
}

Answer 1

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);