Problem Statement:

You are given a list of songs where each song has a duration represented as an integer in seconds. Return the number of pairs of distinct songs such that their total duration in seconds is divisible by 60. Formally, we want the number of indices i, j such that i < j with (duration[i] + duration[j]) % 60 == 0.

Example 1:

Input: [30,20,150,100,40]

Output: 3

Explanation: Three pairs have a total duration divisible by 60: (time[0] = 30, time[2] = 150): total duration 180, index[0, 2], (time[1] = 20, time[3] = 100): total duration 120, index[1, 3], (time[1] = 20, time[4] = 40): total duration 60, index[1, 4].

Solution:

To solve this problem, it is important to recognize that if the remainder of the sum of two durations is equal to zero when divided by 60, then we can say that both durations are divisible by 60. So, we can create a frequency counter that keeps track of the number of durations that have a remainder of time % 60 equal to each possible value from 0 to 59.

We can then loop through the input list, and for each duration, we can calculate the complement duration that we need to find a pair with a total duration divisible by 60. The complement duration would be 60 minus the remainder of the current duration when divided by 60. We can check the frequency counter for the complement duration, and add the number of pairs of durations if it exists in the counter.

Detailed Steps:

1. Initialize the frequency counter to 0 for all possible values of time % 60 from 0 to 59.

2. Loop through the input list and for each duration, do the following:

   • Calculate the remainder of the duration when divided by 60: current_remainder = duration % 60.
   • Calculate the complement duration: complement_duration = (60 - current_remainder) % 60.
   • Add the frequency count of the complement_duration to the number of pairs with a total duration divisible by 60.

3. Return the total number of pairs that have a total duration divisible by 60.

Here's the Python implementation of the above algorithm:

def numPairsDivisibleBy60(time): # Initialize the frequency counter remainder_count = [0] * 60

# Loop through the input list and count the remainders
total_pairs = 0
for duration in time:
    current_remainder = duration % 60
    complement_duration = (60 - current_remainder) % 60
    total_pairs += remainder_count[complement_duration]
    remainder_count[current_remainder] += 1

return total_pairs

Example

time = [30,20,150,100,40] print(numPairsDivisibleBy60(time)) # Output: 3

Time Complexity: O(n), where n is the length of the input list. Space Complexity: O(1), as we are using a fixed-size frequency counter of length 60.

1