Problem Description

You are given a list of integers time, where each element represents the duration (in seconds) of a song. Your task is to find the number of pairs of songs for which the total duration is divisible by 60. In other words, count the number of pairs (i, j) with i < j such that (time[i] + time[j]) % 60 == 0.

• Each song can be used in at most one pair (no reuse of elements).
• There may be multiple valid pairs, and the answer should be the total count of all such pairs.
• The input list time can be of any length, including zero.

Example:
Given time = [30,20,150,100,40], the output should be 3 because there are three pairs whose sums are divisible by 60: (30,150), (20,100), and (20,40).

Thought Process

The most direct way to solve this problem is to check all possible pairs of songs and count those whose total duration is divisible by 60. This brute-force approach involves two nested loops, which can be slow for large lists.

However, there is a mathematical pattern: two numbers sum to a multiple of 60 if and only if the sum of their remainders modulo 60 is also 60 (or 0). For example, if one song's duration modulo 60 is 20, then to form a valid pair, we need another song whose duration modulo 60 is 40, because 20 + 40 = 60.

By counting how many songs have each possible remainder (from 0 to 59), we can efficiently compute how many valid pairs exist without checking every possible pair.

Solution Approach

To efficiently solve the problem, we use the following steps:

1. Count Remainders: For each song duration, compute duration % 60 and keep a count of how many times each remainder occurs. This can be stored in an array or hash map.
2. Pair Remainders: For each possible remainder r from 1 to 29, its complement is 60 - r. The number of valid pairs is the product of the counts for r and 60 - r.
3. Special Cases:
   • When the remainder is 0, pairs can be formed within this group. The number of ways to pick 2 out of n is n * (n - 1) / 2.
   • Similarly, for remainder 30, pairs can be formed within this group in the same way.
4. Sum All Pairs: Add up all pairs from the above steps to get the total count.
5. Why a Hash Map or Array? We use a hash map (or array of size 60) for O(1) lookup and update of remainder counts, making the solution efficient.

Example Walkthrough

Let's walk through the example time = [30, 20, 150, 100, 40]:

1. Compute remainders:
   • 30 % 60 = 30
   • 20 % 60 = 20
   • 150 % 60 = 30
   • 100 % 60 = 40
   • 40 % 60 = 40
   Remainder counts: 20 (1), 30 (2), 40 (2)
2. Find pairs:
   • Remainder 20 pairs with 40: 1 (count of 20) * 2 (count of 40) = 2 pairs: (20,100), (20,40)
   • Remainder 30 pairs with itself: 2 songs with remainder 30 can form 1 pair: 2 * 1 / 2 = 1 pair: (30,150)
3. Total pairs: 2 + 1 = 3

Thus, the function should return 3.

Time and Space Complexity

Brute-force Approach:

• Time Complexity: O(n²), since we check every pair of songs.
• Space Complexity: O(1), as we use only a counter variable.

• Time Complexity: O(n), as we make a single pass to count remainders, and another constant-time pass to compute pairs.
• Space Complexity: O(1), since the remainder count array or hash map has a fixed size of 60.

This optimization is possible because the modulo operation reduces the problem to only 60 possible categories, regardless of input size.

Summary

By recognizing that only the remainders modulo 60 matter, we can efficiently count pairs of songs whose total duration is divisible by 60. Using a hash map or fixed-size array to count remainders, and simple arithmetic to count valid pairs, we avoid the inefficiency of brute-force. This approach is both elegant and highly efficient, making it suitable for large input sizes.

Code Implementation

class Solution:
    def numPairsDivisibleBy60(self, time):
        remainder_count = [0] * 60
        for t in time:
            remainder_count[t % 60] += 1

        count = 0
        # Pairs where remainder is 0
        count += remainder_count[0] * (remainder_count[0] - 1) // 2
        # Pairs where remainder is 30
        count += remainder_count[30] * (remainder_count[30] - 1) // 2
        # Pairs where remainder is r and 60-r
        for r in range(1, 30):
            count += remainder_count[r] * remainder_count[60 - r]
        return count
      

class Solution {
public:
    int numPairsDivisibleBy60(vector<int>& time) {
        vector<int> remainder_count(60, 0);
        for (int t : time) {
            remainder_count[t % 60]++;
        }
        int count = 0;
        // Pairs where remainder is 0
        count += remainder_count[0] * (remainder_count[0] - 1) / 2;
        // Pairs where remainder is 30
        count += remainder_count[30] * (remainder_count[30] - 1) / 2;
        // Pairs where remainder is r and 60-r
        for (int r = 1; r < 30; ++r) {
            count += remainder_count[r] * remainder_count[60 - r];
        }
        return count;
    }
};
      

class Solution {
    public int numPairsDivisibleBy60(int[] time) {
        int[] remainderCount = new int[60];
        for (int t : time) {
            remainderCount[t % 60]++;
        }
        int count = 0;
        // Pairs where remainder is 0
        count += remainderCount[0] * (remainderCount[0] - 1) / 2;
        // Pairs where remainder is 30
        count += remainderCount[30] * (remainderCount[30] - 1) / 2;
        // Pairs where remainder is r and 60-r
        for (int r = 1; r < 30; ++r) {
            count += remainderCount[r] * remainderCount[60 - r];
        }
        return count;
    }
}
      

var numPairsDivisibleBy60 = function(time) {
    let remainderCount = new Array(60).fill(0);
    for (let t of time) {
        remainderCount[t % 60]++;
    }
    let count = 0;
    // Pairs where remainder is 0
    count += remainderCount[0] * (remainderCount[0] - 1) / 2;
    // Pairs where remainder is 30
    count += remainderCount[30] * (remainderCount[30] - 1) / 2;
    // Pairs where remainder is r and 60-r
    for (let r = 1; r < 30; ++r) {
        count += remainderCount[r] * remainderCount[60 - r];
    }
    return count;
};