Problem statement

A playlist is described by time, where time[i] is the length of song i in seconds.

Count the pairs of indices (i, j) with i < j such that the two songs together last a whole number of minutes — that is, (time[i] + time[j]) % 60 == 0.

Example 1

Input: time = [60,60,60]
Output: 3
Explanation: Every pair sums to 120 seconds.

Example 2

Input: time = [10,50,70,110]
Output: 4
Explanation: `10+50`, `10+110`, `50+70` and `70+110` are all multiples of 60.

Example 3

Input: time = [25,7]
Output: 0

Constraints

• 1 <= time.length <= 6 * 10^4
• 1 <= time[i] <= 500

Hints for Pairs of Songs With Total Durations Divisible by 60

1. Hint 1

   Only each duration's remainder modulo 60 matters.

2. Hint 2

   A song with remainder r completes a pair with any earlier song whose remainder is (60 - r) % 60.

3. Hint 3

   Scan once, keeping a count of each remainder seen so far; add the matching count before recording the current song.

How to solve Pairs of Songs With Total Durations Divisible by 60

Two durations sum to a multiple of 60 exactly when their remainders mod 60 add up to 0 or 60, so pairs can be counted by remainder in one pass.

Approach

1. Keep cnt[0..59], the number of earlier songs with each remainder.
2. For each song, let r = time[i] % 60.
3. Add cnt[(60 - r) % 60] to the answer — every earlier song with the complementary remainder forms a valid pair.
4. Then increment cnt[r].

Why it works

Each valid pair (i, j) with i < j is counted exactly once: at index j, when i is already in the table with the complementary remainder. The % 60 on the complement maps remainder 0 to itself, so songs that are exact minutes pair with each other.

Complexity

• Time — O(n)
• Space — O(60)

Pitfalls

• Without the outer % 60, a remainder of 0 looks for cnt[60], which is out of range.
• Counting cnt[r] * cnt[60 - r] afterwards needs special handling for remainders 0 and 30 (pairs within one bucket).
• With up to 6 10^4 songs the count reaches about 1.8 10^9 — it still fits in a 32-bit int, but only just.

Reference solution

Python

from typing import List

def numPairsDivisibleBy60(time: List[int]) -> int:
    cnt = [0] * 60
    pairs = 0
    for t in time:
        r = t % 60
        pairs += cnt[(60 - r) % 60]
        cnt[r] += 1
    return pairs

Java

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

C++

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

JavaScript

var numPairsDivisibleBy60 = function(time) {
    var cnt = new Array(60).fill(0);
    var pairs = 0;
    for (var i = 0; i < time.length; i++) {
        var r = time[i] % 60;
        pairs += cnt[(60 - r) % 60];
        cnt[r]++;
    }
    return pairs;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Implement Router Medium
• Design Memory Allocator Medium
• Design a Food Rating System Medium
• Design an ATM Machine Medium
• Design Bitset Medium
• Range Frequency Queries Medium