Scale Engineer

Pairs of Songs With Total Durations Divisible by 60

Med
#0964Time: 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.7 companies
Patterns
Counting
Data structures
ArrayHash Table
Companies
AkamaiAtlassianDocusignPayPal

Prompt

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 * 104
  • 1 <= 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 count to 0.
  • Iterate through the time array with an index i from 0 to n-1 (where n is the length of the array).
  • Start a nested loop with an index j from i+1 to n-1 to 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.

Solutions

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;  }}

Video 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.

← Previous

Previous problem

Next →

Next problem