In a list of songs, the i-th song has duration of time[i] seconds. Return the number of pairs of songs for which their total duration in seconds is divisible by 60

In a list of songs, the i-th song has duration of time[i] seconds. Return the number of pairs of songs for which their total duration in seconds is divisible by 60. Formally, we want the number of indices i < j with (time[i] + time[j]) % 60 == 0).

Example:

Input array:
10, 20, 30, 60, 80, 110, 120
Output:
Number of such pairs:
2
Pairs are:
10, 110
60, 120

Of course, there is a naïve solution using brute force technique. It's as simple as checking sum for every possible pair with a time complexity of O(n^2).

Efficient solution can be done using mathematical concepts of congruent modulo and combinatorics.

Let's revise what are the cases for a pair sum divisible by 60

Both the numbers of the pair divisible by 60.

The sum of their congruent modulo 60 is divisible by 60.

So actually all the elements of the array can be grouped by congruent modulo. Since it’s modulo 60. Maximum remainder can be 59. Remainders can be any number between 0 to 59.

We actually group all the elements based on modulo value.

Declare group[60]={0}; //since their can be 60 possible remainders starting from 0 to 59

For I in input array group[i%60]++;

In this way our group is formed. If group[j] is K, that simply means there are K elements in the array for each of them modulo 60 is j

Now we need to pick pairs from the group such that pair sum can be divisible by 60

How can we pick?

Pick any from group[1] and group [59] //for first no remainder is 1, second remainder is 59 (1+59=60, divisible by 60)

Pick any from group[2] and group [58] //for first no remainder is 2, second remainder is 58 (2+58=60, divisible by 60)

Pick any from group[3] and group [57] //for first no remainder is 3, second remainder is 57(3+57=60, divisible by 60)

......................continue till group[29] and group[31]......................

Now two groups are remaining group[30] and group[60] This two groups are independent group We can pick any two elements from group[30] Same for group[0] We are done...

For group[30] and group[0]

Possible combinations are (n/2) where n be the respective values for group[30] and group[0] And for 1-29 condition Pick one from first group and one from second group Which is n1*n2 //n1=first group item no, n2=second group item no

For the above example

Only combination possible is from

group[10] and group[50] //1,1 elements respectively

group[0] //2 elements

C++ implementation:

#include <bits/stdc++.h>
using namespace std;
int numPairsDivisibleBy60(vector<int> time) {
//group[60] renamed as a[60]
int count=0;
int a[60]={0};
for(int i=0;i<time.size();i++){
a[time[i]%60]++;
}
int i=1,j=59;
while(i<j){ //for rules 1-29
count+=a[i]*a[j];
i++;
j--;
}
//for group[30] and group[0]
count+=(a[0]*(a[0]-1)/2)+(a[30]*(a[30]-1)/2);
return count;
}
int main(){
int n,item;
cout<<"Number of times to be entered:\n";
cin>>n;
cout<<"Enter times...\n";
vector<int> time;
while(n--){
cin>>item;
time.push_back(item);
}
cout<<"number of such pairs possible is: "
cout<<numPairsDivisibleBy60(time)<<endl;
return 0;
}

Output

Number of times to be entered:
7
Enter times...
10 20 30 60 80 110 120
number of such pairs possible is: 2

Of course, there is a naïve solution using brute force technique. It's as simple as checking sum for every possible pair with a time complexity of

O(n^2).Efficient solution can be done using mathematical concepts of congruent modulo and combinatorics.

Let's revise what are the cases for a pair sum divisible by 60

So actually all the elements of the array can be grouped by congruent modulo.

Since it’s modulo 60.

Maximum remainder can be 59.

Remainders can be any number between 0 to 59.

We actually group all the elements based on modulo value.

group[i%60]++;

In this way our group is formed.

If group[j] is K, that simply means there are K elements in the array for each of them modulo 60 is j

So after grouping,

Now we need to pick pairs from the group such that pair sum can be divisible by 60

How can we pick?

......................continue till group[29] and group[31]......................

Now two groups are remaining

group[30] and group[60]

This two groups are independent group

We can pick any two elements from group[30]

Same for group[0]

We are done...

For group[30] and group[0]

Possible combinations are (n/2) where n be the respective values for group[30] and group[0]

And for 1-29 condition

Pick one from first group and one from second group

Which is n1*n2 //n1=first group item no, n2=second group item no

For the above example

Only combination possible is from

C++ implementation:Output