Pairs of Songs With Total Durations Divisible by 60

Patrick Leaton

Published: Sept. 22, 2021, 8:56 p.m.

Problem 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 * 10^4
1 <= time[i] <= 500

The description was taken from https://leetcode.com/problems/pairs-of-songs-with-total-durations-divisible-by-60.

Problem Solution

#O(N) Time, O(1) Space

class Solution:

    def numPairsDivisibleBy60(self, time: List[int]) -> int:

        seen = collections.defaultdict(int)

        count = 0

        for song in time:

            if song % 60 == 0:

                count += seen[0]

            else:

                complement = 60 - (song % 60)

                count += seen[complement]

            seen[song % 60] += 1

        return count

Problem Explanation

In this question, we are looking at pairs of numbers that can divide into a specific value, sixty.

When we see a requirement like this, similar to Four-Sum II, a HashMap is typically a good approach.

Similar to the Two-Sum problem, we will utilize the x+y=z algorithm, solving for y, which becomes y=z-x, y is the current song's complement duration, x is the current song duration, and z is sixty, the target.

Let's start by initializing a seen dictionary to store the remainders of each song duration divided by sixty.

seen = collections.defaultdict(int)

Next, we will initialize the count of songs we were able to pair that divide evenly by sixty.

count = 0

Then, we will iterate through each song in the list.

If the song divides evenly by sixty, we will just increment the count by however many numbers we have seen that divide evenly by sixty, since this new song addition will allow for a unique pair with each other song that also divides evenly.

if song % 60 == 0: count += seen[0]

Otherwise, we will see if the current song's complement exists in the hashmap. For example, in example one we have [30,20,150,100,40].

In the first iteration, we have thirty. 60 - (30 % 60) = 30.

We will save the remainder, that thirty, so that later when we come across one hundred and fifty, we see that we have that thirty saved and can pair these two songs together to get a sum that divides evenly by sixty.

So, if the current song duration does not divide evenly by sixty, we will calculate the remainder we would need to get to sixty, which is the complement, then we would increase the count by however many of those remainders we have seen so far.

else: complement = 60 - (song%60) count += seen[complement]

Once we have incremented the count in either two situations, we will cache the current remainder.

seen[song%60] += 1

Once we have traversed the entire array and counted each pair, we will return the count of pairs that divide evenly by sixty.

return count