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] <= 500In #1010 Pairs of Songs With Total Durations Divisible by 60, the goal is to count how many song pairs have a total duration divisible by 60. A key observation is that instead of comparing every pair, we can work with the remainder when each duration is divided by 60.
If a song has remainder r, it needs another song with remainder (60 - r) % 60 to form a valid pair. By maintaining a frequency structure (such as a hash table or fixed array of size 60) for previously seen remainders, we can quickly determine how many complementary songs already exist.
As we iterate through the list once, we update counts and accumulate valid pairs. This avoids the inefficient O(n^2) brute-force comparison of all pairs. The optimized counting approach runs in linear time while using only a small constant amount of additional space.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Remainder Counting with Hash Table / Array | O(n) | O(60) ≈ O(1) |
| Brute Force Pair Checking | O(n^2) | O(1) |
Techdose
Use these hints if you're stuck. Try solving on your own first.
We only need to consider each song length modulo 60.
We can count the number of songs having same (length % 60), and store that in an array of size 60.
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.
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.
1function numPairsDivisibleBy60(time) {
2 let remainder = new Array(60).fill(0);
3 let count
In this JavaScript version, we maintain an array to track the count of each remainder. Using a for-of loop, we iterate through each song duration and update our result based on the complement of the current remainder value.
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.
Time Complexity: O(N^2), iterating over every possible pair.
Space Complexity: O(1), with no additional space used apart from the input array.
public class SongPairsBruteForce {
public static int NumPairsDivisibleBy60(int[] time) {
int count = 0;
for (int i = 0; i < time.Length - 1; i++) {
for (int j = i + 1; j < time.Length; j++) {
if ((time[i] + time[j]) % 60 == 0) {
count++;
}
}
}
return count;
}
public static void Main() {
int[] time = new int[] {30, 20, 150, 100, 40};
Console.WriteLine(NumPairsDivisibleBy60(time));
}
}Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Using modulo 60 helps group song durations by their remainder when divided by 60. Two songs form a valid pair if their remainders add up to 60 (or both are 0), making the total duration divisible by 60.
Yes, this problem is a common interview question because it tests understanding of modular arithmetic, hash-based counting, and optimization from brute-force to linear time solutions.
A hash table or a fixed-size array of length 60 works best to store counts of remainders. Since the remainder range is small, an array is often preferred for faster constant-time access.
The optimal approach uses the remainder of each song duration when divided by 60. By tracking frequencies of remainders and pairing each remainder with its complement (60 - r) % 60, we can count valid pairs efficiently in one pass.
The C# solution implements a straightforward nested loop to iterate over song pairs, incrementing the valid pair count when their sums are divisible by 60.