Solution: Pairs of Songs With Total Durations Divisible by 60

Statement

You are given a list of songs, where the duration of each song is represented by an integer array time, where time[i] indicates the length of the $i^{th}$ song in seconds.

Your task is to find and return the number of pairs of songs (i, j) such that:

• i < j (i.e., the pair should consist of two distinct songs)

• The sum of their durations is divisible by 60, i.e., (time[i] + time[j]) % 60 == 0.

Constraints:

• $1 \leq$ time.length $\leq 1000$

• $1 \leq$ time[i] $\leq 500$

Solution

The problem involves finding pairs of song durations whose sum is divisible by 60. The key is to track the remainder of each song’s duration when divided by 60 because these remainders determine pairs. For two songs to meet this condition, one of two scenarios must be true:

1. Both songs have a remainder of 0 (i.e., both are divisible by 60).

2. Their remainders add up to 60 (e.g., both have a remainder of 30).

We use an array, remainders of size 60, where each index represents a remainder (0 to 59) when a song duration is divided by 60. The value at each index stores the count of how many songs have that remainder. For each song, we calculate t % 60 and check if a previously seen song has a complementary remainder to form a valid pair.

The steps of the algorithm are given below:

1. Initialize variables:

   1. remainders: This is an array of size 60 to track how many songs have each possible remainder.

   2. count: This is a variable to keep track of the total number of valid pairs.

2. Loop through the array and for each song duration t in the array:

   1. Calculate the remainder by computing t % 60.

   2. Check for a valid pair:

      1. If t % 60 == 0, the song duration is divisible by 60. In this case, we look for previously encountered songs with a remainder of 0 (i.e., stored in remainders[0]). If so, the number of such songs is added to count, as each can form a valid pair with the current song.

      2. Otherwise, the song has a non-zero remainder, so we look for a song with a remainder that complements the current one (i.e., 60 - (t % 60)), and such songs are added to the count, as each can form a valid pair with the current song.

   3. After checking for valid pairs, update the remainders array to include the current song’s remainder.

3. After processing all songs, return count, which represents the total number of valid pairs whose durations add up to a multiple of 60.

Let’s look at the following illustration to get a better understanding of the solution: