Pairs of Songs With Total Durations Divisible by 60

class Solution {
    public int countMusicPairs(int[] durations) {
        int mods[] = new int[60];
        int pairs = 0;
        for (int duration: durations) {
            int mod = duration % 60;
            if (mod == 0) {
                pairs += mods[0];
            } else {
                pairs += mods[60 - mod];
            }
            mods[mod]++;
        }
        return pairs;
    }
}

Solve the problem of finding pairs of songs where the total duration of each pair is divisible by 60 using an efficient Java approach. By analyzing each song's duration and leveraging modulo arithmetic, this method efficiently identifies and counts these pairs with minimized computational complexity:

• First, declare an array mods to hold the count of song durations modulo 60.
• Initialize a counter pairs to accumulate the number of qualifying song pairs.
• Loop through each song duration in the array:
  • Calculate the remainder of the duration when divided by 60.
  • If the remainder is 0 (meaning the duration is already divisible by 60), increase the pairs count by the number of songs previously encountered with a remainder of 0.
  • Otherwise, add to pairs the count of previously encountered songs that, when added to the current song, result in a sum divisible by 60.
  • Update the mods array by incrementing the counter at the index corresponding to the current song's remainder.
• The function then returns the total count of qualifying pairs found.

This method provides a focused and streamlined way to calculate pairs without the need for nested loops, thereby improving performance for large datasets. By using the properties of modulo, it efficiently associates songs that can form a pair with others, making the algorithm both intuitive and optimal.

class Solution:
    def countPairsDivisibleBy60(self, time: List[int]) -> int:
        remainder_count = collections.defaultdict(int)
        count_pairs = 0
        for t in time:
            if t % 60 == 0:
                count_pairs += remainder_count[0]
            else:
                count_pairs += remainder_count[60 - t % 60]
            remainder_count[t % 60] += 1
        return count_pairs

You will solve the problem of counting pairs of songs where the total duration of each pair is divisible by 60, effectively managing issues related to handling large lists and modular arithmetic. The Python code defines a function countPairsDivisibleBy60, where an array time representing song durations in seconds serves as the input.

• Initialize a dictionary remainder_count using collections.defaultdict to store the frequency of each remainder when song durations are divided by 60.
• Set count_pairs to 0 to keep track of the number of valid pairs.

Iterate over each duration t in the time list:

1. If t % 60 == 0: This checks if the duration t itself is divisible by 60. If true, add remainder_count[0] to count_pairs because adding a duration that leaves no remainder with another that also leaves no remainder results in a total duration divisible by 60.
2. Otherwise, add the count of durations that would complement t to form a divisible by 60 sum to count_pairs. This is achieved by remainder_count[60 - t % 60].
3. Update the remainder count by incrementing remainder_count[t % 60] by one.

Finally, return count_pairs as the result. This approach ensures efficient matching by leveraging the properties of mod operation and taking advantage of hash table operations, which are average O(1) in time complexity. Thus, the overall code runs in O(n) time, where n is the number of items in the time list.