# Amazon Music Pairs Amazon OA 2023 Solution

## Amazon Music Pairs Amazon OA 2023 Solution

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

Program: Amazon Music Pairs Solution in C++

To solve this problem, we can use a hash table to store the frequencies of all the possible remainders obtained when each duration is divided by 60. We can then calculate the number of pairs by checking the count of remainders that add up to 60, as well as the count of remainders that are zero (which can form pairs only with themselves).

``````#include <iostream>
#include <unordered_map>
using namespace std;

int main() {
int n;
cin >> n;

unordered_map<int, int> freq;
for (int i = 0; i < n; i++) {
int duration;
cin >> duration;
freq[duration % 60]++;
}

int count = 0;
count += freq[0] * (freq[0] - 1) / 2; // count pairs of duration 0
count += freq[30] * (freq[30] - 1) / 2; // count pairs of duration 30
for (int i = 1; i < 30; i++) {
count += freq[i] * freq[60 - i]; // count pairs of other durations
}

cout << count << endl;
return 0;
}
``````

Explanation:

• We first read in the number of songs n.
• We create an empty hash table freq to store the frequencies of the remainders.
• We loop through the n songs and calculate the remainder when each duration is divided by 60. We increment the frequency of that remainder in the hash table.
• We initialize the count of distinct song pairs to zero.
• We first count the number of pairs of songs with a duration of 0, which can form pairs only with themselves. We use the formula n(n-1)/2 to count the number of pairs for a frequency n.
• We do the same for songs with a duration of 30, which can form pairs only with themselves.
• For other durations i from 1 to 29, we count the number of pairs of songs whose durations add up to 60 (i.e. songs with duration i and 60-i). We simply multiply the frequencies of durations i and 60-i to get the count of pairs.
• We output the count of distinct song pairs.

Program: Amazon Music Pairs Solution in Python

The function findPair takes in a list of integers nums representing the durations of songs and returns an integer representing the number of distinct pairs of songs that add up to a multiple of 60 seconds.

The function first initializes a list cts of counts for each possible remainder when a duration is divided by 60. For example, cts[0] will store the count of durations that are exact multiples of 60 seconds, cts[1] will store the count of durations that leave a remainder of 1 when divided by 60 seconds, and so on.

The function then iterates through the list of durations nums and increments the corresponding count in cts for each duration.

Next, the function counts the pairs of durations that add up to 0 or 30 seconds, since these pairs can be chosen from any of the durations that leave a remainder of 0 or 30 when divided by 60. This is done using the formula for counting pairs: n * (n – 1) // 2, where n is the count of durations that leave a remainder of 0 or 30.

Finally, the function iterates through the counts in cts for durations that leave a remainder between 1 and 29 when divided by 60, and adds the count of pairs that add up to 60 seconds (i.e. the count of durations with remainder i multiplied by the count of durations with remainder 60 – i).

The function returns the total count of distinct pairs that add up to a multiple of 60 seconds.

``````def findPair(nums):
res = 0
cts = [0] * 60  # Initialize a list of counts for each possible remainder
for num in nums:
cts[num % 60] += 1  # Increment the count of the remainder of the current number
res += (cts[0] * (cts[0] - 1)) // 2  # Count pairs that add up to 0 (can choose any 2 from cts[0])
res += (cts[30] * (cts[30] - 1)) // 2  # Count pairs that add up to 30 (can choose any 2 from cts[30])
for i in range(1, 30):
res += cts[i] * cts[60 - i]  # Count pairs that add up to 60 (i.e. 60 - i)
return res
``````

Program: Amazon Music Pairs Solution in Java

The findPair method takes an array of integers nums as input and returns an integer which represents the number of distinct song pairs that can be chosen by Amazon Music. The approach used in this Java solution is similar to the Python solution.

First, an integer array cts of size 60 is initialized with all elements set to 0. This array will be used to keep track of the frequency of songs with duration modulo 60. Next, a loop is run over all the songs in nums, and for each song, its duration modulo 60 is calculated and the corresponding count in cts is incremented.

After this, three different cases are considered to calculate the total number of distinct song pairs. The first two cases are for songs with duration 0 and 30 seconds respectively, since these songs can only be paired with each other. The number of pairs for each case is calculated using the formula n(n-1)/2, where n is the frequency of the song duration in cts.

For the third case, a loop is run over all the song durations between 1 and 29 seconds (inclusive). For each duration i, the number of pairs that can be formed with songs of duration 60-i is calculated as the product of their frequencies in cts. The total number of pairs is then incremented by this product.

Finally, the total count of distinct song pairs is returned.

``````public int findPair(int[] nums) {
int[] cts = new int[60];
int res = 0;
for (int a : nums) {
++cts[a % 60];
}
res += cts[0] * (cts[0] - 1) / 2;
res += cts[30] * (cts[30] - 1) / 2;
for (int i = 1; i < 30; ++i) {
res += cts[i] * cts[60 - i];
}
return res;
}
``````