Home » Interview coding problems/challenges

Pairs of songs with total durations divisible by 60

In this article, we are going to see how we can optimize a pair sum problem using combinatorics? Submitted by Radib Kar, on March 26, 2019

Problem statement

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

Solution

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

1. Both the numbers of the pair divisible by 60.
2. 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.

1. Declare group[60]={0}; //since their can be 60 possible remainders starting from 0 to 59
2. 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

So after grouping,

    10, 20, 30, 60, 80, 110, 120
    group[10]=1 //10
    group[20]=2 //20,80
    group[30]=1 //30
    group[50]=1 //110
    group[0]=2 //60,120

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

How can we pick?

1. Pick any from group[1] and group [59] //for first no remainder is 1, second remainder is 59 (1+59=60, divisible by 60)
2. Pick any from group[2] and group [58] //for first no remainder is 2, second remainder is 58 (2+58=60, divisible by 60)
3. 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

1. group[10] and group[50] //1,1 elements respectively
2. 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