1010. Pairs of Songs With Total Durations Divisible by 60

Description

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

Solutions

Solution 1: Math + Counting

If the sum of a pair \((a, b)\) is divisible by \(60\), i.e., \((a + b) \bmod 60 = 0\), then \((a \bmod 60 + b \bmod 60) \bmod 60 = 0\). Let \(x = a \bmod 60\) and \(y = b \bmod 60\), then \((x + y) \bmod 60 = 0\), which means \(y = (60 - x) \bmod 60\).

Therefore, we can iterate over the song list and use an array \(cnt\) of length \(60\) to record the number of occurrences of each remainder \(x\). For the current \(x\), if there exists a remainder \(y = (60 - x) \bmod 60\) in array \(cnt\), we add \(cnt[y]\) to the answer. Then we increment the count of \(x\) in array \(cnt\) by \(1\). We continue iterating until the entire song list has been traversed.

After the iteration, we get the number of song pairs that satisfy the condition.

The time complexity is \(O(n)\) and the space complexity is \(O(C)\), where \(n\) is the length of the song list and \(C\) is the number of possible remainders, here \(C = 60\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution:
    def numPairsDivisibleBy60(self, time: List[int]) -> int:
        cnt = Counter()
        ans = 0
        for x in time:
            x %= 60
            y = (60 - x) % 60
            ans += cnt[y]
            cnt[x] += 1
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
    public int numPairsDivisibleBy60(int[] time) {
        int[] cnt = new int[60];
        int ans = 0;
        for (int x : time) {
            x %= 60;
            int y = (60 - x) % 60;
            ans += cnt[y];
            ++cnt[x];
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
public:
    int numPairsDivisibleBy60(vector<int>& time) {
        int cnt[60]{};
        int ans = 0;
        for (int x : time) {
            x %= 60;
            int y = (60 - x) % 60;
            ans += cnt[y];
            ++cnt[x];
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

func numPairsDivisibleBy60(time []int) (ans int) {
    cnt := [60]int{}
    for _, x := range time {
        x %= 60
        y := (60 - x) % 60
        ans += cnt[y]
        cnt[x]++
    }
    return
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

function numPairsDivisibleBy60(time: number[]): number {
    const cnt: number[] = new Array(60).fill(0);
    let ans: number = 0;
    for (let x of time) {
        x %= 60;
        const y = (60 - x) % 60;
        ans += cnt[y];
        ++cnt[x];
    }
    return ans;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

impl Solution {
    pub fn num_pairs_divisible_by60(time: Vec<i32>) -> i32 {
        let mut cnt = [0i32; 60];
        let mut ans: i32 = 0;
        for mut x in time {
            x %= 60;
            let y = (60 - x) % 60;
            ans += cnt[y as usize];
            cnt[x as usize] += 1;
        }
        ans
    }
}

Comments