Pairs of Songs With Total Durations Divisible by 60 #6 Most Asked
Medium
1 view
Topics:
Arrays
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] <= 500
Solution
Clarifying Questions
When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:
- What are the constraints on the size of the input array `time` and the range of values within it?
- Can the array `time` contain zero or negative values?
- If no pairs sum to a multiple of 60, should I return 0?
- Are we looking for distinct pairs, or can the same element be used in multiple pairs?
- Is the order of the elements in the array significant?
Brute Force Solution
Approach
The brute force strategy for this problem involves checking every possible pair of songs to see if their combined duration is divisible by 60. It's like trying every handshake at a party and noting the ones that happen at a multiple of 60 seconds. We will go through each possible pairing to test this divisibility.
Here's how the algorithm would work step-by-step:
- Take the first song's duration.
- Pair it with every other song's duration, one at a time.
- For each pair, add their durations together.
- Check if the total duration of the pair can be divided evenly by 60 (meaning there's no remainder).
- If the total duration is divisible by 60, count that pair as a valid combination.
- Move to the next song and repeat the process, pairing it with all the remaining songs.
- Continue this process until every possible pair of songs has been checked.
Code Implementation
def get_number_of_pairs_brute_force(song_durations):
number_of_pairs = 0
# Iterate through each song duration
for first_song_index in range(len(song_durations)):
# Pair the current song with every other song after it
for second_song_index in range(first_song_index + 1, len(song_durations)):
sum_of_durations = song_durations[first_song_index] + song_durations[second_song_index]
# Check if the sum is divisible by 60
if sum_of_durations % 60 == 0:
# Increment the number of pairs if divisible by 60
number_of_pairs += 1
return number_of_pairsBig(O) Analysis
Time Complexity
O(n²) – The provided brute force approach involves iterating through each song duration in the input array of size n and pairing it with every subsequent song duration. For each of the n songs, we potentially compare it with up to n-1 other songs. This process of checking all possible pairs leads to a nested loop structure where the outer loop runs n times and the inner loop runs approximately n times on average. Thus, the total number of operations is proportional to n * n, resulting in a time complexity of O(n²).
Space Complexity
O(1) – The provided algorithm iterates through pairs of song durations but doesn't use any auxiliary data structures that scale with the input size N (the number of songs). It only uses a few variables for indexing and counting pairs, which require a constant amount of space. Therefore, the space complexity is constant, irrespective of the number of songs. This means the auxiliary space remains O(1).
Optimal Solution
Approach
The key is to avoid checking every possible pair of songs. Instead, we focus on how much each song's duration is short of being a multiple of 60, and count how many songs can complement it to reach that multiple.
Here's how the algorithm would work step-by-step:
- Figure out what each song needs to reach a full 60 minutes (or another multiple of 60). For example, if a song is 70 seconds long, it needs 50 more seconds.
- Keep track of how many songs need each possible amount to reach a multiple of 60. Think of it like counting how many songs need 1 second, 2 seconds, 3 seconds and so on, up to 59 seconds.
- Now, for each song, look up how many other songs can complete it to form a multiple of 60. If a song needs 20 seconds, check how many songs need 40 seconds. The number of matches you find is the number of pairs that song can form.
- Be careful: if a song needs 0 seconds (meaning it's already a multiple of 60), count how many *other* songs also need 0 seconds to avoid counting pairs twice. Similarly, make sure you don't count a song pairing with itself.
- Add up all the matches you found for each song. This total will be the number of pairs whose total duration is a multiple of 60.
Code Implementation
def get_number_of_pairs(song_durations):
number_of_songs = len(song_durations)
count_of_pairs = 0
needed_times = [0] * 60
for song_duration in song_durations:
needed_time = song_duration % 60
needed_times[needed_time] += 1
for song_duration in song_durations:
needed_time = song_duration % 60
complement_time = (60 - needed_time) % 60
# Count songs that can complete the current song.
count_of_pairs += needed_times[complement_time]
# Adjust for self-pairing or double counting.
if needed_time == complement_time:
count_of_pairs -= 1
# Divide the total count by 2 to avoid double-counting pairs
return count_of_pairs // 2
Big(O) Analysis
Time Complexity
O(n) – The algorithm iterates through the input array of size n once to calculate the remainders when divided by 60 and store the counts of each remainder. Then, it iterates through the array again, checking the count of the complementary remainder. Both iterations are linear with respect to n, and the lookup operation in the count array is O(1). Therefore, the overall time complexity is dominated by the linear iterations, resulting in O(n).
Space Complexity
O(1) – The algorithm uses a frequency counter (a dictionary or array) to store the count of song durations modulo 60. The possible remainders when dividing by 60 range from 0 to 59, meaning the size of the counter is fixed at 60, irrespective of the number of songs (N). Therefore, the space required for this counter is constant. No other data structures are used that scale with the input size, so the overall auxiliary space complexity is O(1).
Edge Cases
| Case | How to Handle |
|---|---|
| Empty or null input array | Return 0 since no pairs are possible with an empty array. |
| Array with a single element | Return 0 since a pair requires at least two elements. |
| Array with all elements being multiples of 60 (e.g., all 60, 120, 180) | The algorithm should correctly count all possible pairs in this scenario using combinations. |
| Array with no pairs that sum to a multiple of 60 | The algorithm should return 0 when no valid pairs exist. |
| Large input array with durations close to the maximum integer value | Ensure the intermediate sum of durations does not cause integer overflow. |
| Input array contains zero values | Zero values should be handled correctly when paired with multiples of 60. |
| Very large array (e.g., 10^5 elements) to test for time complexity | Solution needs to be optimized for O(n) time complexity, avoiding brute-force approaches. |
| Array with a mix of durations, some near 0 and others near MAX_INT | Algorithm should correctly handle pairs involving both extremely small and large values. |
Empty or null input array
How to Handle:
Return 0 since no pairs are possible with an empty array.
Array with a single element
How to Handle:
Return 0 since a pair requires at least two elements.
Array with all elements being multiples of 60 (e.g., all 60, 120, 180)
How to Handle:
The algorithm should correctly count all possible pairs in this scenario using combinations.
Array with no pairs that sum to a multiple of 60
How to Handle:
The algorithm should return 0 when no valid pairs exist.
Large input array with durations close to the maximum integer value
How to Handle:
Ensure the intermediate sum of durations does not cause integer overflow.
Input array contains zero values
How to Handle:
Zero values should be handled correctly when paired with multiples of 60.
Very large array (e.g., 10^5 elements) to test for time complexity
How to Handle:
Solution needs to be optimized for O(n) time complexity, avoiding brute-force approaches.
Array with a mix of durations, some near 0 and others near MAX_INT
How to Handle:
Algorithm should correctly handle pairs involving both extremely small and large values.
0/0 Citrix questions completed
0/0 completed
Explore Interview QuestionsGoogle Interview QuestionsMeta Interview QuestionsAmazon Interview QuestionsApple Interview QuestionsNetflix Interview Questions
Explore Jobs By LevelEntry-Level Software Engineer JobsMid-Level Software Engineer JobsSenior Software Engineer JobsStaff Software Engineer Jobs
