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
belongs to collection: Interview C++ coding problems/challenges | arrays
All Answers
total answers (1)
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