Arrays
Basically, the problem asks how many combinations of two are there. In this case, we care about only modulo 60 of each value. Using a hash table to count modulo 60 values is a key to solve this problem.
You are given a list of songs where 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
such thati < j
with(time[i] + time[j]) % 60 == 0
.Constraints:
1 <= time.length <= 6 * 10**4
1 <= time[i] <= 500
https://leetcode.com/problems/pairs-of-songs-with-total-durations-divisible-by-60/
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.
The first step is to count modulo 60 values. If modulo 60 is 0 or 30, within that value, two pairs can be created. So, n * (n - 1) / 2 is the number of combinations. If modulo 60 and 60 - modulo 60 are there, for example, 20 and 40, combinations are number of 20 times number of 40. To avoid the pair doubly, up to 30 condition is added.
class PairOfSongsWithTotalDurationsDivisibleBy60:
def numPairsDivisibleBy60(self, time: List[int]) -> int:
counter = collections.Counter([t % 60 for t in time])
result = 0
for k, v in counter.items():
if k == 0 or k == 30:
result += (v * (v - 1) // 2)
elif k < 30 and 60 - k in counter:
result += (v * counter[60 - k])
return result
O(m + n)
– m: length of given array, n: distinct values of x % 60O(n)