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

- 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

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?

- 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

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions