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.
This approach uses the idea of complementary remainders. If the sum of the remainders of two numbers when divided by 60 equals 60, then their sum is divisible by 60. For example, if the remainder of a number A is 10, you would need a number B whose remainder is 50 to ensure their sum is divisible by 60 (since 10 + 50 = 60).
We can leverage this by keeping a count of all remainders encountered so far and for each number, check for its complement remainder that, when added, will result in a number divisible by 60.
The C solution uses an array 'remainder' to store counts of remainders of each number in the input divided by 60. For each element, it checks how many elements with a complementary remainder have been seen so far and adds that count to the total.
Time Complexity: O(N), where N is the number of songs.
Space Complexity: O(1), since we use a fixed-size array of size 60.
In this approach, we use a brute force double loop to compare each pair of songs. For each song, pair it with every other song that comes after it and check if their total duration is divisible by 60. This is a straightforward method but inefficient for large inputs.
Although simple, this method is not optimal for large datasets but can work if constraints are smaller.
The brute force C solution uses nested loops to compute every possible pair of songs and checks if their combined duration is divisible by 60. This results in a simple, albeit inefficient solution.
Time Complexity: O(N^2), iterating over every possible pair.
Space Complexity: O(1), with no additional space used apart from the input array.
If the sum of a pair (a, b) is divisible by 60, i.e., (a + b) bmod 60 = 0, then (a bmod 60 + b bmod 60) bmod 60 = 0. Let x = a bmod 60 and y = b bmod 60, then (x + y) bmod 60 = 0, which means y = (60 - x) bmod 60.
Therefore, we can iterate over the song list and use an array cnt of length 60 to record the number of occurrences of each remainder x. For the current x, if there exists a remainder y = (60 - x) bmod 60 in array cnt, we add cnt[y] to the answer. Then we increment the count of x in array cnt by 1. We continue iterating until the entire song list has been traversed.
After the iteration, we get the number of song pairs that satisfy the condition.
The time complexity is O(n) and the space complexity is O(C), where n is the length of the song list and C is the number of possible remainders, here C = 60.
| Approach | Complexity |
|---|---|
| Using Complementary Remainders | Time Complexity: O(N), where N is the number of songs. |
| Brute Force Approach | Time Complexity: O(N^2), iterating over every possible pair. |
| Math + Counting | — |
| 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 |
Pairs of songs with total durations divisible by 60 | Leetcode #1010 • Techdose • 27,237 views views
Watch 9 more video solutions →Practice Pairs of Songs With Total Durations Divisible by 60 with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor