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

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 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.

Approach

Input: An integer array time

Output: Return the number of combinations that sum to a multiple of 60

This is a Hash Table + Array problem.

We can use a hash table or an array to store the quantity of numbers mod 60 in the array.

When the iterated number mod 60 is mod, and we can find the quantity of 60 - mod in the hash table, it means they can form a multiple of 60. Add this count: res += count[60 - mod].

Record the value of the current number mod 60 down each time. Note the special handling for mod = 0. To handle mod = 0 elegantly, we can use complement = (60 - mod) % 60.

Implementation

python

class Solution:
    def numPairsDivisibleBy60(self, time: List[int]) -> int:
        count = [0] * 60  # Record the number of times each remainder appears
        res = 0

        for t in time:
            mod = t % 60
            complement = (60 - mod) % 60  # Complementary remainder

            # How many "complementary remainders" the current duration can pair with
            res += count[complement]

            # Record the current remainder for future numbers to pair with
            count[mod] += 1

        return res

javascript

/**
 * @param {number[]} time
 * @return {number}
 */
var numPairsDivisibleBy60 = function(time) {
    const count = Array(60).fill(0);

    let ans = 0;
    for (let t of time) {
        const mod = t % 60;

        const complement = (60 - mod) % 60;

        ans += count[complement];

        count[mod] += 1;
    }

    return ans;
};

Complexity Analysis

• Time Complexity: O(n)
• Space Complexity: O(1) space since array size is fixed at 60

Links

1010. Pairs of Songs With Total Durations Divisible by 60 (English)1010. 总持续时间可被 60 整除的歌曲 (Chinese)