Pairs of Songs With Total Durations Divisible by 60

Similar Problems:

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 <= time.length <= 60000
- 1 <= time[i] <= 500

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

- Solution:

// https://code.dennyzhang.com/pairs-of-songs-with-total-durations-divisible-by-60 // Basic Ideas: hashmap for limited value range // Complexity: Time O(n), Space O(1) func numPairsDivisibleBy60(time []int) int { l := make([]int, 60) for _, value := range time { l[value%60]++ } res := (l[0]*(l[0]-1))/2 + (l[30]*(l[30]-1))/2 for i:= 1; i<30; i++ { res += l[i]*l[60-i] } return res }