Watch 10 video solutions for Pairs of Songs With Total Durations Divisible by 60, a medium level problem involving Array, Hash Table, Counting. This walkthrough by Techdose has 27,237 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given a list of songs where the ith song has a duration of time[i] seconds.
Return the number of pairs of songs for which their total duration in seconds is divisible by 60. Formally, we want the number of indices i, j such that i < j with (time[i] + time[j]) % 60 == 0.
Example 1:
Input: time = [30,20,150,100,40] Output: 3 Explanation: Three pairs have a total duration divisible by 60: (time[0] = 30, time[2] = 150): total duration 180 (time[1] = 20, time[3] = 100): total duration 120 (time[1] = 20, time[4] = 40): total duration 60
Example 2:
Input: time = [60,60,60] Output: 3 Explanation: All three pairs have a total duration of 120, which is divisible by 60.
Constraints:
1 <= time.length <= 6 * 1041 <= time[i] <= 500Problem Overview: You receive an integer array time where each value represents the duration of a song in seconds. The goal is to count how many pairs of songs have a total duration divisible by 60. Two songs form a valid pair if (time[i] + time[j]) % 60 == 0 and i < j.
Approach 1: Brute Force Pair Check (O(n2) time, O(1) space)
The straightforward method checks every possible pair of songs. Use two nested loops: the outer loop picks the first song and the inner loop scans the remaining songs. For each pair, compute (time[i] + time[j]) % 60 and increment a counter when the result equals zero. This approach requires no extra data structures and is easy to implement, but the quadratic time complexity becomes slow when the input size grows. It mainly helps verify correctness before optimizing.
Approach 2: Complementary Remainders with Hash Counting (O(n) time, O(60) space)
The key observation is that only the remainder of each duration modulo 60 matters. If a song has remainder r, it needs another song with remainder (60 - r) % 60 to make the total divisible by 60. Maintain a frequency array or hash map that counts how many songs have each remainder from 0 to 59. As you iterate through the array, compute the current remainder and immediately add the number of previously seen complementary remainders to the answer. Then update the frequency of the current remainder.
This works because every valid pair is discovered exactly once during the single pass. Special handling is naturally covered: remainder 0 pairs with 0, and remainder 30 pairs with 30. The algorithm processes each element once and performs constant‑time lookups, producing an efficient linear solution. The idea is a classic counting trick commonly used in array and hash table problems, especially when solving modular pairing tasks using counting techniques.
Recommended for interviews: Interviewers expect the complementary remainder counting approach. It shows that you recognize modular arithmetic patterns and can convert a pair problem into a frequency lookup. Mentioning the brute force method first demonstrates baseline reasoning, but implementing the O(n) remainder counting solution demonstrates stronger algorithmic insight.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Pair Check | O(n^2) | O(1) | Useful for small inputs or to validate logic before optimizing |
| Complementary Remainder Counting (Hash/Array) | O(n) | O(60) | Best general solution; single pass with constant-time remainder lookups |