Music Pairs

 Amazon Music Pairs

Amazon Music is working on a new "community radio station" feature which will allow users to iteratively populate
the playlist with their desired songs. Considering this radio station will also have other scheduled shows to be
aired, and to make sure the community soundtrack will not run over other scheduled shows, the user-submitted songs
will be organized in full-minute blocks. Users can choose any songs they want to add to the community list, but
only in pairs of songs with durations that add up to a multiple of 60 seconds (e.g. 60, 120, 180).

As an attempt to insist on the highest standards and avoid this additional burden on users, Amazon will let them
submit any number of songs they want, with any duration, and will handle this 60-second matching internally. Once
the user submits their list, given a list of song durations, calculate the total number of distinct song pairs that
can be chosen by Amazon Music.

Solution:

The pair is disguised by their indexes. So if they have the same value but on different positions, then we still consider them different.

For example, [60, 60, 60], there will be 3 pairs which are (0, 1), (0, 2), and (1, 2) in indexes.

So the naïve solution is O(N^2), we just use a two-layer for loop, for each pair, check their sum can be divided by 60. But this is not the interviewer want.

A better way can reach O(N).

We  just need to get the remainders of each element, for example, [60, 60, 60] will becomes [0, 0, 0]. Then we know there are 3 elements that can be divided by 60. So we just need to pick 2 of them to form a pair, so there will be n*(n-1)/2 pairs.

In other cases, if we have x with count of a and (60 - x) with count of b, then we can form a*b pairs.

So in summary:

1): get the remainders of each elements;

2): count the number of each remainders;

3): analyze the counts to find the valid pair

The time complexity is O(N), and space complexity is O(N).

See the code below:

int findPair(vector<int>& nums) {
	int res = 0;
	vector<int> cts(60, 0);
	for(auto &a : nums) ++cts[a%60];
	for(int i=1; i<30; ++i) res += cts[i]*cts[60-i];
	res += cts[0]*(cts[0]-1)/2 + cts[30]*(cts[30]-1)/2;
	return res; 
}