Pairs of Songs With Total Durations Divisible by 60

medium hash map counting modular arithmetic

Problem

You are given a list of song durations time in seconds. Return the number of pairs of songs (i, j) with i < j such that their total duration is divisible by 60, i.e. (time[i] + time[j]) % 60 == 0.

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

Output3

Pairs: (30, 150), (20, 100), (20, 40) — remainders 30+30, 20+40, 20+40 all sum to a multiple of 60.

time (comma-separated)

def num_pairs_divisible_by_60(time):
    count = [0] * 60
    pairs = 0
    for t in time:
        r = t % 60
        need = (60 - r) % 60
        pairs += count[need]
        count[r] += 1
    return pairs

function numPairsDivisibleBy60(time) {
  const count = new Array(60).fill(0);
  let pairs = 0;
  for (const t of time) {
    const r = t % 60;
    const need = (60 - r) % 60;
    pairs += count[need];
    count[r] += 1;
  }
  return pairs;
}

class Solution {
    public int numPairsDivisibleBy60(int[] time) {
        int[] count = new int[60];
        int pairs = 0;
        for (int t : time) {
            int r = t % 60;
            int need = (60 - r) % 60;
            pairs += count[need];
            count[r]++;
        }
        return pairs;
    }
}

int numPairsDivisibleBy60(vector<int>& time) {
    vector<int> count(60, 0);
    int pairs = 0;
    for (int t : time) {
        int r = t % 60;
        int need = (60 - r) % 60;
        pairs += count[need];
        count[r]++;
    }
    return pairs;
}

Explanation

Two songs pair up when their durations add to a multiple of 60. The only thing that matters for divisibility is each song's remainder modulo 60, so we work with r = t % 60 instead of the full time.

For a song with remainder r, its partner must have the complementary remainder need = (60 - r) % 60 — the extra % 60 handles the case r = 0, whose partner is also 0. We keep a count array of how many earlier songs had each remainder.

As we scan, we first add count[need] to pairs (every earlier matching song pairs with this one), then record this song with count[r]++. Counting before recording avoids pairing a song with itself.

Example: time = [30, 20, 150, 100, 40] → remainders 30, 20, 30, 40, 40. The 150 (r=30) matches the earlier 30; the 100 (r=40) matches the 20; the 40 (r=40) matches the 20 as well — that is 3 pairs.

Because each song does constant work against a fixed 60-slot table, the whole count is a single linear pass.

Time: O(n) Space: O(1)