Pairs of Songs With Total Durations Divisible by 60
MedPrompt
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 60Example 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] <= 500
Approaches
2 approaches with complexity analysis and trade-offs.
The most straightforward approach is to check every possible pair of songs. We can use nested loops to iterate through all unique pairs (i, j) where i < j, and for each pair, we check if the sum of their durations is divisible by 60.
Algorithm
- Initialize a counter
countto 0. - Iterate through the
timearray with an indexifrom 0 ton-1(wherenis the length of the array). - Start a nested loop with an index
jfromi+1ton-1to form unique pairs(i, j). - Inside the inner loop, calculate the sum
time[i] + time[j]. - Check if
(time[i] + time[j]) % 60 == 0. - If the condition is true, increment the
count. - After the loops complete, return
count.
Walkthrough
This method involves a brute-force check of all possible pairs of songs. We use two nested loops to generate every unique pair of indices (i, j) such that i < j. For each pair, we sum their durations time[i] + time[j] and check if this sum is divisible by 60 using the modulo operator. If it is, we increment a counter. This process continues until all pairs have been checked.
class Solution { public int numPairsDivisibleBy60(int[] time) { int count = 0; int n = time.length; for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { if ((time[i] + time[j]) % 60 == 0) { count++; } } } return count; }}Complexity
Time
O(N^2), where N is the number of songs. For each song, we iterate through the rest of the songs to find a pair, resulting in nested loops.
Space
O(1), as we only use a constant amount of extra space for the counter and loop variables.
Trade-offs
Pros
Simple to understand and implement.
Requires no extra space other than a counter variable.
Cons
Highly inefficient for large inputs, leading to Time Limit Exceeded (TLE) errors.
The time complexity is quadratic, making it impractical for the given constraints.
A more efficient approach leverages modular arithmetic. The condition (a + b) % 60 == 0 is equivalent to (a % 60 + b % 60) % 60 == 0. We can iterate through the list of song durations once, keeping track of the frequencies of the remainders when divided by 60. For each song, we find how many other songs we've already seen that can complete a pair.
Algorithm
- Initialize a variable
pairsto 0. - Create an integer array
remaindersof size 60, initialized to all zeros. This array will store the frequency of each remainder modulo 60. - Iterate through each duration
tin the inputtimearray. - Calculate the remainder of the current duration:
r = t % 60. - Determine the complement remainder needed to make a sum divisible by 60. If
ris 0, the complement is 0. Otherwise, it's60 - r. This can be concisely written ascomplement = (60 - r) % 60. - Add the number of songs with the complement remainder found so far to the total count:
pairs += remainders[complement]. - Increment the count for the current remainder in the frequency map:
remainders[r]++. - After iterating through all the songs, return the total
pairscount.
Walkthrough
This optimized solution relies on a key mathematical property: if (t1 + t2) % 60 == 0, then (t1 % 60 + t2 % 60) % 60 == 0. This means we only need to consider the remainders of the song durations when divided by 60.
We can use an array of size 60 as a frequency map to store the counts of songs for each possible remainder (0 to 59). We iterate through the time array once. For each song duration t, we first calculate its remainder r = t % 60. Then, we determine the complement remainder c that would make a pair divisible by 60. This complement is (60 - r) % 60. The number of songs we have already seen with this complement remainder c is the number of new pairs we can form with the current song. We add this count to our total. Finally, we update the frequency map by incrementing the count for the current song's remainder r.
This single-pass approach correctly counts all pairs (i, j) with i < j because when we process time[j], we are looking for complements among time[0...j-1] which have already been recorded in the frequency map.
class Solution { public int numPairsDivisibleBy60(int[] time) { int[] remainders = new int[60]; int count = 0; for (int t : time) { int r = t % 60; int complement = (60 - r) % 60; count += remainders[complement]; remainders[r]++; } return count; }}Complexity
Time
O(N), where N is the number of songs. We iterate through the `time` array only once.
Space
O(1). We use an auxiliary array of size 60 to store the frequencies of remainders. Since the size of this array is constant and does not depend on the input size N, the space complexity is constant.
Trade-offs
Pros
Highly efficient with a linear time complexity.
Uses constant extra space, making it suitable for large inputs.
Cons
Slightly more complex to understand than the brute-force approach.
Requires careful handling of the modulo arithmetic, especially for the case where the remainder is 0.
Solutions
Solution
class Solution {public int numPairsDivisibleBy60(int[] time) { int[] cnt = new int[60]; for (int t : time) { ++cnt[t % 60]; } int ans = 0; for (int x = 1; x < 30; ++x) { ans += cnt[x] * cnt[60 - x]; } ans += (long)cnt[0] * (cnt[0] - 1) / 2; ans += (long)cnt[30] * (cnt[30] - 1) / 2; return ans; }}class Solution {public: int numPairsDivisibleBy60(vector<int> &time) { int cnt[60]{}; for (int &t : time) { ++cnt[t % 60]; } int ans = 0; for (int x = 1; x < 30; ++x) { ans += cnt[x] * cnt[60 - x]; } ans += 1LL * cnt[0] * (cnt[0] - 1) / 2; ans += 1LL * cnt[30] * (cnt[30] - 1) / 2; return ans; }};class Solution: def numPairsDivisibleBy60(self, time: List[int]) -> int: cnt = Counter(t % 60 for t in time) ans = sum(cnt[x] * cnt[60 - x] for x in range(1, 30)) ans += cnt[0] * (cnt[0] - 1) // 2 ans += cnt[30] * (cnt[30] - 1) // 2 return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.