How do you solve Pairs of Songs With Total Durations Divisible by 60?

Iterate through the list once, computing the remainder of each duration modulo 60. For each remainder, calculate the needed complement remainder to reach 60 (or 0 if remainder is 0). Use a hash map to track counts of each remainder seen so far. Increment the pair count by the number of complements found. Update the hash map with the current remainder. Return the total pair count after processing all songs.

What pattern does Pairs of Songs With Total Durations Divisible by 60 use?

The Pattern: Hash Maps (Frequency Counting with Modular Arithmetic) The Heuristic: When a problem involves pairing elements based on a sum divisible by a number, transform the problem into counting complementary remainders using a hash map to achieve O(n) time complexity.

Pairs of Songs With Total Durations Divisible by 60

Q: What is the time complexity of Pairs of Songs With Total Durations Divisible by 60?

O(n). The algorithm iterates through the list once, performing O(1) hash map operations per element, resulting in linear time complexity.

Problem

Given a list of song durations in seconds, return the number of pairs of songs for which the total duration is divisible by 60.

1 ≤ time.length ≤ 6 * 10⁴
1 ≤ time[i] ≤ 500

Example

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

Output: 3

The pairs are (30, 150), (20, 100), and (20, 40). The sum of each pair is divisible by 60. A brute-force approach would check all pairs, resulting in O(n^2) time. The optimal approach uses modular arithmetic and a hash map to count complements efficiently.

Approach

Straightforward Solution

A brute-force approach checks every pair of songs, summing their durations and checking divisibility by 60. This requires O(n^2) time and is too slow for large inputs.

Core Observation

Two numbers sum to a multiple of 60 if and only if their remainders modulo 60 add up to 60 (or both are zero). This modular pairing property is the foundation for an efficient solution.

Path to Optimal

Preview

The key insight is to use the modulo operation to reduce the problem to counting pairs of remainders that sum to 60…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Iterate through the list once, computing the remainder of each duration modulo 60. For each remainder, calculate the needed complement remainder to reach 60 (or 0 if remainder is 0)…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(n)

The algorithm iterates through the list once, performing O(1) hash map operations per element, resulting in linear time complexity.

Space

O(1)

The hash map stores counts for at most 60 possible remainders, which is a fixed constant, so auxiliary space is O(1).

Solution

Python

1class Solution:
2    def numPairsDivisibleBy60(self, time: list[int]) -> int:
3        remainder_counts = {}
4        pair_count = 0
5
6        for duration in time:
7            remainder = duration % 60
8            needed_remainder = (60 - remainder) % 60
9
10            pair_count += remainder_counts.get(needed_remainder, 0)
11            remainder_counts[remainder] = remainder_counts.get(remainder, 0) + 1
12
13        return pair_count

Step-by-Step Solution

1

Track Remainder Frequencies and Count Valid Pairs

3remainder_counts = {}
4pair_count = 0
6for duration in time:
7    remainder = duration % 60
8    needed_remainder = (60 - remainder) % 60
10    pair_count += remainder_counts.get(needed_remainder, 0)
11    remainder_counts[remainder] = remainder_counts.get(remainder, 0) + 1
13return pair_count

Objective

To maintain counts of song durations modulo 60 and accumulate the number of valid pairs efficiently in a single pass.

Key Insight

By computing the remainder of each song duration modulo 60, the problem reduces to finding pairs of remainders that sum to 60. Using a hash map to store frequencies of each remainder seen so far allows constant-time lookup of the complement remainder needed to form a divisible pair. Incrementing the pair count by the frequency of the complement remainder before updating the current remainder count ensures all valid pairs are counted exactly once.

Interview Quick-Check

Core Logic

For each song, compute remainder modulo 60, find complement remainder (60 - remainder) % 60, add the count of complement remainder seen so far to the pair count, then update the current remainder count.

State & Boundaries

Handle the special case where remainder is 0 by using modulo operation to keep complement in range [0,59].

Common Pitfalls & Bugs

Forgetting to use modulo operation on complement remainder can cause incorrect indexing, especially when remainder is 0.

Complexity

This approach runs in O(n) time and O(1) space since the hash map size is bounded by 60.

Line Analysis

This solution has 3 Critical lines interviewers watch for.

Line 10 Critical

pair_count += remainder_counts.get(needed_remainder, 0)

Increment the pair count by the number of previously seen songs with the complement remainder.

This is the definitive algorithmic move that enables O(n) counting of valid pairs by leveraging the hash map to instantly find how many complements exist, eliminating the need for nested loops.

Line 8 Critical

needed_remainder = (60 - remainder) % 60

Calculate the complement remainder needed to reach a multiple of 60.

This calculation is critical because it correctly handles the edge case where the remainder is zero, ensuring the complement is also zero, which is necessary for accurate pairing.

Line 11 Critical

remainder_counts[remainder] = remainder_counts.get(remainder, 0) + 1

Update the hash map with the current remainder count.

The order of updating after counting complements is crucial to avoid counting pairs twice or pairing a song with itself.

Full line-by-line criticality + rationale for all 8 lines available on Pro.

Test Your Understanding

Why does using the modulo 60 remainder and its complement allow counting pairs in a single pass?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Pairs of Songs With Total Durations Divisible by 60 from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Pairs of Songs With Total Durations Divisible by 60 drill

or drill a free problem

1	`class Solution:`
2	`def numPairsDivisibleBy60(self, time: list[int]) -> int:`
3	`remainder_counts = {}`
4	`pair_count = 0`
5
6	`for duration in time:`
7	`remainder = duration % 60`
8	`needed_remainder = (60 - remainder) % 60`
9
10	`pair_count += remainder_counts.get(needed_remainder, 0)`
11	`remainder_counts[remainder] = remainder_counts.get(remainder, 0) + 1`
12
13	`return pair_count`

3	`remainder_counts = {}`
4	`pair_count = 0`
6	`for duration in time:`
7	`remainder = duration % 60`
8	`needed_remainder = (60 - remainder) % 60`
10	`pair_count += remainder_counts.get(needed_remainder, 0)`
11	`remainder_counts[remainder] = remainder_counts.get(remainder, 0) + 1`
13	`return pair_count`