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:

(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

Function shape:

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

Examples

Example 1:

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

The valid pairs are:

So the answer is:

3

Example 2:

time = [60, 60, 60]

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

Answer:

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:

(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

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

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:

r = t % 60

Check how many previous songs have the complementary remainder:

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:

count[r] += 1

Testing

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()