1010. Pairs of Songs With Total Durations Divisible by 60
Problem Description
In this problem, you are given a list of songs with their play durations in seconds. Your task is to find out how many unique pairs of songs have total durations that are divisible by 60. Specifically, if you have two distinct indices i
and j
such that i < j
, you need to count the number of pairs (time[i], time[j])
where the sum of their durations is a multiple of 60 seconds. Mathematically, this means that (time[i] + time[j]) % 60 == 0
.
Intuition
The intuition behind the solution draws from the modular arithmetic properties. Any time two numbers add up to a multiple of 60, their remainder when divided by 60 must also add up to either 60 or 0. In other words, if one song has a remainder of r
when divided by 60, then we need to find another song that has a remainder of 60 - r
.
The approach is made efficient by using the following methodology:
- We first create a counter that holds how many times each remainder occurs when we divide each song's length by 60.
- We iterate over the possible remainders from 1 to 29. Why? Because each unique pair's remainders would add up to 60, and we don't need to check beyond 30 since 30's pair would be 30 itself and that would result in double counting.
- For each remainder
x
, we find its complementary remainder60-x
. The number of pairs that can be formed with these remainders is the product of their occurrences:cnt[x] * cnt[60 - x]
. - We separately calculate pairs for the songs which themselves are a multiple of 60 (
cnt[0]
). These form pairs with themselves, and thus the number of such combinations iscnt[0] * (cnt[0] - 1) / 2
. - We perform a similar calculation for the songs which have a remainder of 30 seconds, since they also pair with themselves, and the number of combinations is
cnt[30] * (cnt[30] - 1) / 2
. - We sum up these results to get the total number of valid pairs.
In summary, we use a counting method and leverage the property of numbers and their remainders when dividing by 60 to efficiently calculate the total number of pairs.
Solution Approach
The solution is implemented in Python and uses several key concepts to optimize the counting of song pairs:
-
Hash Table (Counter): The
Counter
class from Python'scollections
module is used to keep track of how many times each remainder occurs when the song lengths are divided by 60. Hash tables allow for efficient lookup, insertion, and update of the count, which is crucial for this problem.Example: If
time = [30, 20, 150, 100, 40]
, thencnt
after modulo and counting will be{30: 1, 20: 1, 30: 1, 40: 1, 40: 1}
which simplifies the process of finding complements. -
Modular Arithmetic:
- The core principle used here is that if two numbers
a
andb
satisfy(a + b) % 60 == 0
, thena % 60 + b % 60
must equal either0
or60
. - For each remainder from 1 to 29, we find its complement
60 - x
and calculate possible pairs between them.
- The core principle used here is that if two numbers
-
Special Cases for Remainders 0 and 30:
- For songs that are exactly divisible by 60 (
remainder == 0
), they can only pair up with other songs that are also exactly divisible by 60. The number of such pairs is a combination count calculated bycnt[0] * (cnt[0] - 1) / 2
, using the formulan * (n - 1) / 2
for pairs. - The same logic applies to songs with a remainder of 30 since they also pair with themselves. This is calculated by
cnt[30] * (cnt[30] - 1) / 2
.
- For songs that are exactly divisible by 60 (
-
Summation of Pairs:
- The total number of pairs is calculated by summing the pairs formed by remainders
x
and60 - x
forx
from 1 to 29, and the special case pairs where the remainder is exactly 0 or 30. - This is achieved by iterating through range 1 to 29, and adding the special cases separately, followed by returning the sum as the final answer.
- The total number of pairs is calculated by summing the pairs formed by remainders
The implementation cleverly avoids double-counting by ensuring that pairs are only counted once by considering only x
from 1 to 29 and calculating the complement pairs directly. It also deals with the edge cases where the song lengths are either a multiple of 60 or half of 60. The use of the Counter data structure, modulo operation, and understanding of how remainders can be paired provides an efficient and elegant solution to the problem.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's assume we have the following list of song durations in seconds: time = [60, 20, 120, 100, 40]
. We want to find how many unique pairs of songs have total durations that are divisible by 60.
Following the solution approach given in the problem content:
-
Use a Counter to tally remainders: First, we take the modulo 60 of each duration to find the remainder, and we create a counter to hold how many times each remainder occurs. Doing this for our example, we get:
- The remainders for
[60, 20, 120, 100, 40]
after modulo 60 are[0, 20, 0, 40, 40]
. - Thus, the counter
cnt
becomes{0: 2, 20: 1, 40: 2}
.
- The remainders for
-
Calculate pairs for remainders from 1 to 29: We iterate over the possible remainders and find the count of their complements. For our example, the relevant remainders and their complements are:
- For remainder
20
: The complement is60 - 20 = 40
. - The count for remainder
20
is1
, and the count for its complement40
is2
. - Thus, the number of pairs with remainders that would add up to 60 is
1 * 2 = 2
.
- For remainder
-
Special cases for remainders 0 and 30: We check for the special cases:
- For remainder
0
: There are 2 songs with a duration that is perfectly divisible by 60. - The number of pairs among them is
cnt[0] * (cnt[0] - 1) / 2
, which in numbers is2 * (2 - 1) / 2 = 1
. - In this example, there is no song with remainder
30
so we do not have that case.
- For remainder
-
Summation of pairs: Finally, we sum all the counts for valid pairs to get the total number of pairs which are divisible by 60.
- From steps 2 and 3, we have
2 + 1 = 3
pairs.
- From steps 2 and 3, we have
In conclusion, the example time
list has 3
unique pairs of songs that have total durations which are divisible by 60, which are the pairs (60, 100)
, (20, 40)
, and (20, 40)
(note that the last two pairs are different because they represent different indices in the list, not the same pair counted twice).
Solution Implementation
1from collections import Counter
2
3class Solution:
4 def numPairsDivisibleBy60(self, time: List[int]) -> int:
5 # Create a counter of time durations modulo 60
6 count = Counter(t % 60 for t in time)
7
8 # Initialize pairs count
9 pairs_count = 0
10
11 # Iterate over each minute value in the range [1, 29]
12 # Each value x has a complementary value (60 - x) to form a divisible pair
13 for x in range(1, 30):
14 pairs_count += count[x] * count[60 - x]
15
16 # Add the number of pairs where the time duration is exactly 0 modulo 60
17 # Because these can be paired with each other, calculate using combination formula n * (n - 1) / 2
18 pairs_count += count[0] * (count[0] - 1) // 2
19
20 # Add the number of pairs where the time duration is exactly 30 modulo 60
21 # Apply the same combination formula since 30 + 30 is divisible by 60
22 pairs_count += count[30] * (count[30] - 1) // 2
23
24 # Return the total count of divisible pairs
25 return pairs_count
26
1class Solution {
2 public int numPairsDivisibleBy60(int[] times) {
3 int[] count = new int[60]; // Create an array to store counts for each remainder when divided by 60
4
5 // Count the occurrences of each remainder when the song lengths are divided by 60
6 for (int time : times) {
7 count[time % 60]++;
8 }
9
10 int numberOfPairs = 0; // Initialize the number of pairs that are divisible by 60
11
12 // For each pair of remainders (x, 60-x), calculate the number of valid combinations
13 for (int i = 1; i < 30; i++) {
14 numberOfPairs += count[i] * count[60 - i];
15 }
16
17 // Add the special cases where the remainders are exactly 0 or 30 (since 30 + 30 = 60)
18 // Calculate combinations using the formula n * (n - 1) / 2 for each special case
19 numberOfPairs += count[0] * (count[0] - 1) / 2; // Pairs where both times have no remainder
20 numberOfPairs += count[30] * (count[30] - 1) / 2; // Pairs where both times leave a remainder of 30
21
22 // Return the total number of pairs that have song lengths summing to a multiple of 60
23 return numberOfPairs;
24 }
25}
26
1class Solution {
2public:
3 int numPairsDivisibleBy60(vector<int>& times) {
4 // Initialize a count array to store the frequency of each remainder when divided by 60
5 int remainderCount[60] = {};
6
7 // Fill the frequency array by computing the remainder of each time div by 60
8 for (int& time : times) {
9 ++remainderCount[time % 60];
10 }
11
12 int pairsCount = 0; // To store the total number of pairs
13
14 // Iterate through possible remainders from 1 to 29. We don't need to consider
15 // remainders from 31 to 59 because they have been already counted with their
16 // complementary remainders (59 with 1, 58 with 2, etc.)
17 for (int i = 1; i < 30; ++i) {
18 // Add to the pair count the product of the frequencies of complementary remainders.
19 // Each pair from remainder i can form a divisible pair with a time from remainder 60-i.
20 pairsCount += remainderCount[i] * remainderCount[60 - i];
21 }
22
23 // We need to handle the special cases for remainders 0 and 30 separately because
24 // these can form pairs with themselves. We use the combination formula nC2 = n*(n-1)/2
25 // to calculate the number of ways to pick 2 out of n times.
26
27 // Add pairs with both times having remainder 0
28 pairsCount += static_cast<long long>(remainderCount[0]) * (remainderCount[0] - 1) / 2;
29 // Add pairs with both times having remainder 30.
30 pairsCount += static_cast<long long>(remainderCount[30]) * (remainderCount[30] - 1) / 2;
31
32 // Return the total count of pairs divisible by 60
33 return pairsCount;
34 }
35};
36
1// Function to find the number of pairs of songs that have
2// total durations divisible by 60
3function numPairsDivisibleBy60(times: number[]): number {
4 // Array to store the count of times modulo 60
5 const countMod60: number[] = new Array(60).fill(0);
6 // Populate the count array with the time modulo 60
7 for (const time of times) {
8 ++countMod60[time % 60];
9 }
10
11 // Variable to store the result: the number of valid pairs
12 let totalPairs = 0;
13
14 // Find all pairs where the sum of time % 60 is 60
15 for (let x = 1; x < 30; ++x) {
16 totalPairs += countMod60[x] * countMod60[60 - x];
17 }
18
19 // Add pairs where the time % 60 is 0 (these pair with themselves)
20 totalPairs += (countMod60[0] * (countMod60[0] - 1)) / 2;
21
22 // Add pairs where the time % 60 is 30 (these pair with themselves)
23 totalPairs += (countMod60[30] * (countMod60[30] - 1)) / 2;
24
25 // Return the total number of valid pairs
26 return totalPairs;
27}
28
Time and Space Complexity
Time Complexity
The time complexity of the given code can be broken down into a few parts:
-
The creation of the counter
cnt
that stores the frequencies of each remainder when thetime
elements are divided by 60. This requires one pass over thetime
list, which makes this partO(N)
whereN
is the length oftime
. -
The summation
sum(cnt[x] * cnt[60 - x] for x in range(1, 30))
iterates from 1 to 29, which is a constant number of iterations. Therefore, this part takesO(1)
time, as the range does not depend on the size of the input. -
The last two lines calculate the pairs for the special cases where the elements are directly divisible by 60 (remainder is 0) and the pairs where the remainders are exactly 30. These calculations are also done in constant time
O(1)
.
Combining all these, since O(N + 1 + 1)
simplifies to O(N)
, the overall time complexity of the code is O(N)
.
Space Complexity
The space complexity of the code is dominated by the space required for the Counter
object cnt
. In the worst case, if all time elements give a different remainder when divided by 60, the counter will contain up to 60 keys (since remainders range from 0 to 59). Therefore, the space complexity is O(1)
because the space required does not grow with N
, it is limited by the constant number 60.
Learn more about how to find time and space complexity quickly using problem constraints.
What's the output of running the following function using input 56
?
1KEYBOARD = {
2 '2': 'abc',
3 '3': 'def',
4 '4': 'ghi',
5 '5': 'jkl',
6 '6': 'mno',
7 '7': 'pqrs',
8 '8': 'tuv',
9 '9': 'wxyz',
10}
11
12def letter_combinations_of_phone_number(digits):
13 def dfs(path, res):
14 if len(path) == len(digits):
15 res.append(''.join(path))
16 return
17
18 next_number = digits[len(path)]
19 for letter in KEYBOARD[next_number]:
20 path.append(letter)
21 dfs(path, res)
22 path.pop()
23
24 res = []
25 dfs([], res)
26 return res
27
1private static final Map<Character, char[]> KEYBOARD = Map.of(
2 '2', "abc".toCharArray(),
3 '3', "def".toCharArray(),
4 '4', "ghi".toCharArray(),
5 '5', "jkl".toCharArray(),
6 '6', "mno".toCharArray(),
7 '7', "pqrs".toCharArray(),
8 '8', "tuv".toCharArray(),
9 '9', "wxyz".toCharArray()
10);
11
12public static List<String> letterCombinationsOfPhoneNumber(String digits) {
13 List<String> res = new ArrayList<>();
14 dfs(new StringBuilder(), res, digits.toCharArray());
15 return res;
16}
17
18private static void dfs(StringBuilder path, List<String> res, char[] digits) {
19 if (path.length() == digits.length) {
20 res.add(path.toString());
21 return;
22 }
23 char next_digit = digits[path.length()];
24 for (char letter : KEYBOARD.get(next_digit)) {
25 path.append(letter);
26 dfs(path, res, digits);
27 path.deleteCharAt(path.length() - 1);
28 }
29}
30
1const KEYBOARD = {
2 '2': 'abc',
3 '3': 'def',
4 '4': 'ghi',
5 '5': 'jkl',
6 '6': 'mno',
7 '7': 'pqrs',
8 '8': 'tuv',
9 '9': 'wxyz',
10}
11
12function letter_combinations_of_phone_number(digits) {
13 let res = [];
14 dfs(digits, [], res);
15 return res;
16}
17
18function dfs(digits, path, res) {
19 if (path.length === digits.length) {
20 res.push(path.join(''));
21 return;
22 }
23 let next_number = digits.charAt(path.length);
24 for (let letter of KEYBOARD[next_number]) {
25 path.push(letter);
26 dfs(digits, path, res);
27 path.pop();
28 }
29}
30
Recommended Readings
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Want a Structured Path to Master System Design Too? Donāt Miss This!