LeetCode 1010. Pairs of Songs With Total Durations Divisible by 60

You are given a list of songs where the ith song has a duration of time[i] seconds.

Return the number of pairs of songs for which their total duration in seconds is divisible by 60. Formally, we want the number of indices i, j such that i < j with (time[i] + time[j]) % 60 == 0.

Example 1:

Input: time = [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
(time[1] = 20, time[3] = 100): total duration 120
(time[1] = 20, time[4] = 40): total duration 60

Example 2:

Input: time = [60,60,60]
Output: 3
Explanation: All three pairs have a total duration of 120, which is divisible by 60.

Constraints:

• 1 <= time.length <= 6 * 104
• 1 <= time[i] <= 500

Solution

We are given a list of time representing the duration of each song in seconds. Our goal is to find the number of pairs of songs that have a total duration that is divisible by 60.

This question is very similar to the 2Sum problem with an added twist of modulo.

The first step is to initialize an array count of size 60 to store the count of songs with a particular duration modulo 60. This array is used to keep track of the frequency of each remainder value, which will be useful later when we want to find pairs that add up to 60.

Next, we iterate through each song duration in time and calculate its remainder when divided by 60. We use this remainder value as an index in the count array to update the frequency count.

For each song duration, we then look for other song durations with a remainder of (60 - t % 60) % 60, since this would result in a total duration that is divisible by 60. We add the count of such song durations to the result, as this would represent the number of pairs that have a total duration that is divisible by 60.

Finally, we return the result as the answer to the problem.

class Solution:
    def numPairsDivisibleBy60(self, time: List[int]) -> int:
        count = [0] * 60
        res = 0
        for t in time:
            res += count[(60 - t % 60) % 60]
            count[t % 60] += 1
        return res

class Solution {
    public int numPairsDivisibleBy60(int[] time) {
        int[] count = new int[60];
        int result = 0;
        
        for (int t : time) {
            int remainder = t % 60;
            result += count[(60 - remainder) % 60];
            count[remainder]++;
        }
        
        return result;
    }
}

class Solution {
public:
    int numPairsDivisibleBy60(vector<int>& time) {
        int count[60] = {0};
        int result = 0;
        
        for (int t : time) {
            int remainder = t % 60;
            result += count[(60 - remainder) % 60];
            count[remainder]++;
        }
        
        return result;
    }
};

The time complexity of this code is O(n), where n is the number of songs in the list. This is because we need to iterate through each song once and perform a constant amount of work for each iteration.

The space complexity of this code is O(60), as we use an array of size 60 to store the count of songs with a particular duration modulo 60. This array only needs to store up to 60 different values, so the space complexity is proportional to the number of possible remainders when dividing by 60.