Problem

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.

Examples

Example 1:

1
2
3
4
5
6

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:

1
2
3

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

Solution

Method 1 - Using Hashtable

The problem requires efficiently finding pairs of song durations that sum up to a multiple of 60. A direct approach using nested loops would lead to O(n^2) complexity, which is computationally expensive for large input sizes. Instead, we use a modulo-based approach with a hash map to store the frequency of remainders modulo 60, reducing the complexity to linear time.

Steps:

  1. Calculate remainder for each song duration: remainder = time[i] % 60.
  2. Keep track of the count of each remainder using an array freq of size 60.
  3. For each song duration:
    • Determine the complement remainder that pairs to form a sum divisible by 60. The complement is (60 - remainder) % 60.
    • Add the count of complement remainder to the answer (ans), then increment the respective freq index for the current duration’s remainder.
  4. Return the total count.
Edge cases
  • If the remainder is 0, the complement is also 0.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {

    public int numPairsDivisibleBy60(int[] time) {
        int[] freq = new int[60];
        int ans = 0;

        for (int t : time) {
            int rem = t % 60;
            int complement = (60 - rem) % 60;
            ans += freq[complement];
            freq[rem]++;
        }

        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution:
    def numPairsDivisibleBy60(self, time: List[int]) -> int:
        freq = [0] * 60
        ans = 0

        for t in time:
            rem = t % 60
            complement = (60 - rem) % 60
            ans += freq[complement]
            freq[rem] += 1

        return ans

Complexity

  • ⏰ Time complexity: O(n) where n is the number of songs (we iterate the list once).
  • 🧺 Space complexity: O(60) which reduces to O(1) (fixed size array for remainders).