# LeetCode 1010: Pairs of Songs With Total Durations Divisible by 60

## Problem Restatement

We are given a list of song durations `time`.

We want to count pairs of songs `(i, j)` where `i < j` and:

```python
(time[i] + time[j]) % 60 == 0
```

We need to return the number of such pairs.

The official constraints state that `1 <= time.length <= 6 * 10^4` and `1 <= time[i] <= 500`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Array `time` of song durations |
| Output | Number of pairs with total duration divisible by 60 |

Function shape:

```python
def numPairsDivisibleBy60(time: list[int]) -> int:
    ...
```

## Examples

Example 1:

```python
time = [30, 20, 150, 100, 40]
```

The valid pairs are:

| Indices | Durations | Sum | Divisible by 60? |
|---|---|---:|---|
| `(0, 2)` | `30 + 150` | `180` | Yes |
| `(1, 3)` | `20 + 100` | `120` | Yes |
| `(1, 4)` | `20 + 40` | `60` | Yes |

So the answer is:

```python
3
```

Example 2:

```python
time = [60, 60, 60]
```

All pairs: `(0,1)`, `(0,2)`, `(1,2)`. Each sum is `120`, divisible by `60`.

Answer:

```python
3
```

## Key Insight

This is analogous to Two Sum, but with modular arithmetic.

For two durations to sum to a multiple of 60, their remainders mod 60 must complement each other:

```python
(r1 + r2) % 60 == 0
```

This means `r2 == (60 - r1) % 60`.

Count frequencies of remainders, then for each duration, look up how many previous durations have the complementary remainder.

## Algorithm

1. Create a `count` array of size `60` initialized to `0`.
2. Initialize `pairs = 0`.
3. For each `t` in `time`:
   - Compute `r = t % 60`.
   - Add `count[(60 - r) % 60]` to `pairs`.
   - Increment `count[r]`.
4. Return `pairs`.

## Correctness

For each song, we count how many previously seen songs have a complementary remainder. This correctly counts unordered pairs because we always look at songs to the left (earlier index) before updating the count.

The modulo `(60 - r) % 60` handles the edge case where `r = 0`: the complement is `0` (not `60`), and `(60 - 0) % 60 = 0`.

## Edge Cases

- Duplicates usually matter; store counts when a set would lose necessary multiplicity.
- Update the frequency structure in the same order the invariant assumes.
- Check empty or one-element inputs if the problem allows them.

## Complexity

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n)` | One pass through the array |
| Space | `O(1)` | Fixed-size count array of 60 |

## Common Pitfalls

- Do not optimize away the invariant; the code should still make it clear what condition is being maintained.
- Prefer problem-specific names over one-letter variables once the logic becomes stateful.

## Implementation

```python
class Solution:
    def numPairsDivisibleBy60(self, time: list[int]) -> int:
        count = [0] * 60
        pairs = 0

        for t in time:
            r = t % 60
            pairs += count[(60 - r) % 60]
            count[r] += 1

        return pairs
```

## Code Explanation

For each song duration `t`, compute its remainder:

```python
r = t % 60
```

Check how many previous songs have the complementary remainder:

```python
pairs += count[(60 - r) % 60]
```

The `% 60` handles the case `r = 0` where the complement is `0`, not `60`.

Update the count for the current remainder:

```python
count[r] += 1
```

## Testing

```python
def run_tests():
    s = Solution()

    assert s.numPairsDivisibleBy60([30, 20, 150, 100, 40]) == 3
    assert s.numPairsDivisibleBy60([60, 60, 60]) == 3
    assert s.numPairsDivisibleBy60([30, 30]) == 1
    assert s.numPairsDivisibleBy60([10, 20, 30]) == 0
    assert s.numPairsDivisibleBy60([60]) == 0

    print("all tests passed")

run_tests()
```

| Test | Expected | Why |
|---|---:|---|
| Standard example | `3` | Three complementary pairs |
| Three 60s | `3` | All three pairs sum to 120 |
| Two 30s | `1` | `30 + 30 = 60` |
| No pairs | `0` | No complementary remainders |
| Single song | `0` | No pairs possible |