Solution: Pairs of Songs With Total Durations Divisible by 60
Let’s solve the Pairs of Songs With Total Durations Divisible by 60 problem using the Knowing What to Track pattern.
We'll cover the following
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
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:
time.length
time[i]
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:
Both songs have a remainder of 0 (i.e., both are divisible by 60).
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:
Initialize variables:
remainders
: This is an array of size 60 to track how many songs have each possible remainder.count
: This is a variable to keep track of the total number of valid pairs.
Loop through the array and for each song duration
t
in the array:Calculate the remainder by computing
t % 60
.Check for a valid pair:
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 inremainders[0]
). If so, the number of such songs is added tocount
, as each can form a valid pair with the current song.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 thecount
, as each can form a valid pair with the current song.
After checking for valid pairs, update the
remainders
array to include the current song’s remainder.
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:
Level up your interview prep. Join Educative to access 80+ hands-on prep courses.