# Pairs of Songs With Total Durations Divisible by 60
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/pairs-of-songs-with-total-durations-divisible-by-60)
Canonical: https://scaleengineer.com/dsa/problems/pairs-of-songs-with-total-durations-divisible-by-60
**Patterns:** [Counting](https://scaleengineer.com/dsa/patterns/counting)
**Data structures:** Array, Hash Table
**Companies:** [Akamai](https://scaleengineer.com/companies/akamai), [Atlassian](https://scaleengineer.com/companies/atlassian), [Docusign](https://scaleengineer.com/companies/docusign), [PayPal](https://scaleengineer.com/companies/paypal), [Salesforce](https://scaleengineer.com/companies/salesforce), [BlackRock](https://scaleengineer.com/companies/blackrock), [Citrix](https://scaleengineer.com/companies/citrix)
---
## 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`.

**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`

# Approaches
## Brute Force Iteration
The most straightforward approach is to check every possible pair of songs. We can use nested loops to iterate through all unique pairs (i, j) where i < j, and for each pair, we check if the sum of their durations is divisible by 60.
**Time:** O(N^2), where N is the number of songs. For each song, we iterate through the rest of the songs to find a pair, resulting in nested loops. · **Space:** O(1), as we only use a constant amount of extra space for the counter and loop variables.
**Pros:** Simple to understand and implement.; Requires no extra space other than a counter variable.
**Cons:** Highly inefficient for large inputs, leading to Time Limit Exceeded (TLE) errors.; The time complexity is quadratic, making it impractical for the given constraints.
### Explanation
This method involves a brute-force check of all possible pairs of songs. We use two nested loops to generate every unique pair of indices `(i, j)` such that `i < j`. For each pair, we sum their durations `time[i] + time[j]` and check if this sum is divisible by 60 using the modulo operator. If it is, we increment a counter. This process continues until all pairs have been checked.

```java
class Solution {
    public int numPairsDivisibleBy60(int[] time) {
        int count = 0;
        int n = time.length;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if ((time[i] + time[j]) % 60 == 0) {
                    count++;
                }
            }
        }
        return count;
    }
}
```
### Algorithm
- Initialize a counter `count` to 0.
- Iterate through the `time` array with an index `i` from 0 to `n-1` (where `n` is the length of the array).
- Start a nested loop with an index `j` from `i+1` to `n-1` to form unique pairs `(i, j)`.
- Inside the inner loop, calculate the sum `time[i] + time[j]`.
- Check if `(time[i] + time[j]) % 60 == 0`.
- If the condition is true, increment the `count`.
- After the loops complete, return `count`.

## Optimized Approach using a Frequency Map
A more efficient approach leverages modular arithmetic. The condition `(a + b) % 60 == 0` is equivalent to `(a % 60 + b % 60) % 60 == 0`. We can iterate through the list of song durations once, keeping track of the frequencies of the remainders when divided by 60. For each song, we find how many other songs we've already seen that can complete a pair.
**Time:** O(N), where N is the number of songs. We iterate through the `time` array only once. · **Space:** O(1). We use an auxiliary array of size 60 to store the frequencies of remainders. Since the size of this array is constant and does not depend on the input size N, the space complexity is constant.
**Pros:** Highly efficient with a linear time complexity.; Uses constant extra space, making it suitable for large inputs.
**Cons:** Slightly more complex to understand than the brute-force approach.; Requires careful handling of the modulo arithmetic, especially for the case where the remainder is 0.
### Explanation
This optimized solution relies on a key mathematical property: if `(t1 + t2) % 60 == 0`, then `(t1 % 60 + t2 % 60) % 60 == 0`. This means we only need to consider the remainders of the song durations when divided by 60.

We can use an array of size 60 as a frequency map to store the counts of songs for each possible remainder (0 to 59). We iterate through the `time` array once. For each song duration `t`, we first calculate its remainder `r = t % 60`. Then, we determine the complement remainder `c` that would make a pair divisible by 60. This complement is `(60 - r) % 60`. The number of songs we have already seen with this complement remainder `c` is the number of new pairs we can form with the current song. We add this count to our total. Finally, we update the frequency map by incrementing the count for the current song's remainder `r`.

This single-pass approach correctly counts all pairs `(i, j)` with `i < j` because when we process `time[j]`, we are looking for complements among `time[0...j-1]` which have already been recorded in the frequency map.

```java
class Solution {
    public int numPairsDivisibleBy60(int[] time) {
        int[] remainders = new int[60];
        int count = 0;
        for (int t : time) {
            int r = t % 60;
            int complement = (60 - r) % 60;
            count += remainders[complement];
            remainders[r]++;
        }
        return count;
    }
}
```
### Algorithm
- Initialize a variable `pairs` to 0.
- Create an integer array `remainders` of size 60, initialized to all zeros. This array will store the frequency of each remainder modulo 60.
- Iterate through each duration `t` in the input `time` array.
- Calculate the remainder of the current duration: `r = t % 60`.
- Determine the complement remainder needed to make a sum divisible by 60. If `r` is 0, the complement is 0. Otherwise, it's `60 - r`. This can be concisely written as `complement = (60 - r) % 60`.
- Add the number of songs with the complement remainder found so far to the total count: `pairs += remainders[complement]`.
- Increment the count for the current remainder in the frequency map: `remainders[r]++`.
- After iterating through all the songs, return the total `pairs` count.

# Solutions
### Java

```java
class Solution {
public
  int numPairsDivisibleBy60(int[] time) {
    int[] cnt = new int[60];
    for (int t : time) {
      ++cnt[t % 60];
    }
    int ans = 0;
    for (int x = 1; x < 30; ++x) {
      ans += cnt[x] * cnt[60 - x];
    }
    ans += (long)cnt[0] * (cnt[0] - 1) / 2;
    ans += (long)cnt[30] * (cnt[30] - 1) / 2;
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int numPairsDivisibleBy60(vector<int> &time) {
    int cnt[60]{};
    for (int &t : time) {
      ++cnt[t % 60];
    }
    int ans = 0;
    for (int x = 1; x < 30; ++x) {
      ans += cnt[x] * cnt[60 - x];
    }
    ans += 1LL * cnt[0] * (cnt[0] - 1) / 2;
    ans += 1LL * cnt[30] * (cnt[30] - 1) / 2;
    return ans;
  }
};

```

### Python

```python
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

```