Pairs of Songs With Total Durations Divisible by 60

MEDIUM

Description

You are given a list of songs where the i^th 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 * 10⁴
1 <= time[i] <= 500

Approaches

Checkout 2 different approaches to solve Pairs of Songs With Total Durations Divisible by 60. Click on different approaches to view the approach and algorithm in detail.

Brute Force Iteration

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.

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 Analysis

Time Complexity: 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 Complexity: O(1), as we only use a constant amount of extra space for the counter and loop variables.

Pros and Cons

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.

Code Solutions

Checking out 3 solutions in different languages for Pairs of Songs With Total Durations Divisible by 60. Click on different languages to view the code.

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 Solution

Watch the video walkthrough for Pairs of Songs With Total Durations Divisible by 60

Patterns:

Counting

Data Structures:

ArrayHash Table

Companies:

Akamai |Atlassian |Docusign |PayPal |