Leetcode: Pairs of Songs With Total Durations Divisible by 60

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

Github: code.dennyzhang.com

Credits To: leetcode.com

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


  • Solution:
// Blog link: 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
}
linkedin
github
slack

Share It, If You Like It.

Leave a Reply

Your email address will not be published.