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

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

• javascript
• algorithm
• time-plexity
• big-o

Share Improve this question Follow edited Jan 14, 2019 at 17:28 ruakh 184k2929 gold badges290290 silver badges323323 bronze badges asked Jan 13, 2019 at 19:43 GAURAV GULATIGAURAV GULATI 5311 silver badge33 bronze badges 3

• A linear implementation of the bination function is okay because it’s linear with respect to the number of elements it represents. So the more work you have to do inside the bination function, the less it runs. – Ry- ♦ Commented Jan 13, 2019 at 19:50
• Your question title seems misleading. It says "find all the pairs that...", but then in your examples you seem to want to "find the count of pairs that...". Please clarify. – trincot Commented Jan 13, 2019 at 22:42
• Remember, that "obj.hasOwnProperty" is not free call either. It would bee more expensive as the number of properties is increasing. – jancha Commented Jan 14, 2019 at 11:55

Add a ment  | 

5 Answers 5

Sorted by: Reset to default 1

There is no bination 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);

You can pute 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)/₂.

That said, you might want to consider a different approach: instead of having a separate loop to pute 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.)

If we count the pairs each element can make with the numbers seen so far, we can use simple addition rather than manage binatorics 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.)

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?

int numPairsDivisibleBy60(vector<int>& time) {
    
    int n = (int)time.size(), ans = 0;
    
    int freq[61]{};

    for(int i = 0; i < n; ++i) 
        freq[time[i] % 60]++;
    
    for(int i = 0; i <= 30; ++i) {
        if(freq[i] >= 1) {
            if(i == 0 or i == 30) {
                ans += freq[i] * 1LL * (freq[i] - 1) / 2;
            } else {
                ans += freq[60 - i] * freq[i];
            }
        }
    }
    
    return ans;

}