1010. Pairs of Songs With Total Durations Divisible by 60

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.

Constraints:

• $1<=time.length<=6\ast 10^4$
• 1 <= time[i] <= 500

From: LeetCode
Link: 1010. Pairs of Songs With Total Durations Divisible by 60

Solution:

Ideas:

• For each song, only its remainder modulo 60 matters.

• If one song has remainder r, it needs another song with remainder:

  • 60 - r, or
  • 0 if r == 0

• Use cnt[x] to record how many previous songs have remainder x.

• For each current song:

  • compute r = time[i] % 60
  • add cnt[(60 - r) % 60] to the answer
  • then record this song with cnt[r]++

Code:

int numPairsDivisibleBy60(int* time, int timeSize) {
    int cnt[60] = {0};
    int ans = 0;

    for (int i = 0; i < timeSize; i++) {
        int r = time[i] % 60;
        int need = (60 - r) % 60;   // handles r == 0

        ans += cnt[need];
        cnt[r]++;
    }

    return ans;
}