1013. Pairs of Songs With Total Durations Divisible by 60

Runtime: 60 ms, faster than 99.70% of Python3 submissions

Memory Usage: 15.6 MB, less than 100.00% of Python3 submissions

In a list of songs, the i-th 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 with (time[i] + time[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
(time[1] = 20, time[3] = 100): total duration 120
(time[1] = 20, time[4] = 40): total duration 60

Example 2:

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

Note:

1. 1 <= time.length <= 60000
2. 1 <= time[i] <= 500

Solution 1: brute force

We can just iterate the whole list with two for loop, say with time[i]and time[j]. If time[i] + time[j] == 60, we count it as 1.

# solution 1
class Solution:
    def numPairsDivisibleBy60(self, time: List[int]) -> int:
        total = 0
        for i, song1 in enumerate(time):
            for j in range(i+1, len(time)):
                if (song1 + time[j]) % 60 == 0:
                    total += 1
        return total

Oops, I get the Time Limit Exceeded error. Our code is inefficient. We should notice that 1 <= time.length <= 60000tell us this time list might be very long. If the list have 40000 elements, we have to run at (1+40000)*40000/2=800020000 times! We have to find some way to reduce this operation.

Solution 2: mod operation (get the remainder)

We can take mod operation for each element in timelist and count its frequency, which will reduce the long time list to a limited dictionary.

from collections import Counter
counts = Counter([x % 60 for x in time]) 
# {20: 1, 30: 2, 40: 2}

Specifically, we will get a dictionary with a maximum length of 60, even if we have a list with 40000 elements.

There are two kinds of the remainder.

• The remainder is 0 or 30. If the remainder is 0, it means the original time might be 60, 120, 180, and so on. We can take any combination of two remainders 0s as a pair. The number of such pair is counts[0]*(counts[0]-1)/2. If the remainder is 30, just like the remainder 0, any combination of two remainders 30 is a pair. The number of such pair is alsocounts[0]*(counts[0]-1)/2.
• The remainder except 0 and 30. If remainder A is 15 and remainder B is 45, the number of such pair is alsocounts[15]*counts[45].

Ok, write the logic with code.

class Solution:
    def numPairsDivisibleBy60(self, time: List[int]) -> int:
        from collections import Counter
        total = 0
        counts = Counter([x % 60 for x in time]) 
        if 30 in counts:
            total += counts[30] * (counts[30] - 1) / 2
            del counts[30]
        if 0 in counts:
            total += counts[0] * (counts[0] - 1) / 2
            del counts[0]
        
        for i in range(1, 30):
            if i in counts and (60-1) in counts:
                total += counts[i] * counts[60-1]
return int(total)

And this solution is not just only fast, but also memory efficient.

Runtime: 60 ms, faster than 99.70% of Python3 submissions

Memory Usage: 15.6 MB, less than 100.00% of Python3 submissions