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

Problem #

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

Problem Summary #

In the song list, the ith song has a duration of time[i] seconds.

Return the number of pairs of songs whose total duration (in seconds) is divisible by 60. Formally, we want indices i and j satisfying i < j and (time[i] + time[j]) % 60 == 0.

Solution Approach #

• Easy problem. First take each element in the array modulo 60, converting all of them to the range [0,59]. Then find pairs of elements in the array whose sum equals 60. You can search for matching pairs by halves within 0-30. Calculate 0 and 30 separately. Because multiple 0s added together still have remainder 0. The sum of two 30s is 60.

Code #

func numPairsDivisibleBy60(time []int) int {
	counts := make([]int, 60)
	for _, v := range time {
		v %= 60
		counts[v]++
	}
	res := 0
	for i := 1; i < len(counts)/2; i++ {
		res += counts[i] * counts[60-i]
	}
	res += (counts[0] * (counts[0] - 1)) / 2
	res += (counts[30] * (counts[30] - 1)) / 2
	return res
}