Leetcode - Pairs of Songs With Total Durations Divisible by 60

violet posted @ Apr 07, 2020 07:07:40 AM in 算法 with tags 2sum Algorithm Golang , 337 阅读

https://leetcode.com/problems/pairs-of-songs-with-total-durations-divisible-by-60/

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

Surprisingly this is a two sum problem. It needs to play some tricks on mod 60.

func numPairsDivisibleBy60(time []int) int {
    count := map[int]int{}
    result := 0
    for _, t := range time {
        d := (60 - t % 60) % 60
        result += count[d]
        count[t%60]++
    }
    return result
}