{x}
blog image

Pairs of Songs With Total Durations Divisible by 60

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

1010. Pairs of Songs With Total Durations Divisible by 60

This problem asks to find the number of pairs of songs from a given list whose total duration is divisible by 60.

Approach 1: Using a Frequency Counter

This approach leverages a frequency counter (using a hash map or array) to efficiently count the remainders when song durations are divided by 60. We then calculate pairs based on these remainders.

Algorithm:

  1. Calculate Remainders: Iterate through the time array and calculate the remainder of each song duration when divided by 60. Store these remainders in a frequency counter (cnt).

  2. Count Pairs:

    • For remainders from 1 to 29, find the pairs (x, 60-x) whose sum is divisible by 60. The number of such pairs is cnt[x] * cnt[60 - x].
    • For remainder 0, we need to find combinations of pairs (0,0) whose sum is divisible by 60. The number of such pairs is cnt[0] * (cnt[0] - 1) / 2 (combinations).
    • Similarly for remainder 30, we need to find combinations of pairs (30,30) whose sum is divisible by 60. The number of such pairs is cnt[30] * (cnt[30] - 1) / 2.

  3. Return Total: Sum up the number of pairs from steps 2.

Time Complexity: O(N), where N is the length of the time array. We iterate through the array once to calculate remainders and once to count pairs.

Space Complexity: O(1). The frequency counter cnt has a fixed size of 60.

Code (Python):

from collections import Counter
 
class Solution:
    def numPairsDivisibleBy60(self, time: List[int]) -> int:
        cnt = Counter(t % 60 for t in time)
        ans = sum(cnt[x] * cnt[60 - x] for x in range(1, 30))
        ans += cnt[0] * (cnt[0] - 1) // 2
        ans += cnt[30] * (cnt[30] - 1) // 2
        return ans

Code in other languages (Java, C++, Go, TypeScript) follows a similar structure, replacing the Python Counter with equivalent data structures (arrays or HashMaps).

Approach 2: Optimized Counting

This approach is slightly more efficient in terms of code and avoids redundant calculations.

Algorithm:

  1. Initialize Counter: Create a frequency counter (cnt) initialized to all zeros.

  2. Iterate and Count: Iterate through the time array. For each song duration x:

    • Calculate the remainder x % 60.
    • Calculate the complement y = (60 - x) % 60.
    • Add the count of songs with remainder y (from the counter) to the total count ans. This represents the number of pairs found so far.
    • Increment the count for the remainder x in the counter.

  3. Return Total: Return the final ans.

Time Complexity: O(N), similar to Approach 1.

Space Complexity: O(1), the space used is constant.

Code (Python):

from collections import Counter
 
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

Again, code in other languages would adapt the counter to the language's built-in structures. This approach is generally preferred for its conciseness and slight efficiency gain.