Jobs

Interviews

Discussions

Pairs of Songs With Total Durations Divisible by 60

Medium

Asked by:

+12

More companies

72 views

Topics:

Arrays

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

Try coding it in LeetCode

Pairs of Songs With Total Durations Divisible by 60

Medium

Asked by:

More companies

72 views

Topics:

Arrays

You are given a list of songs where the i^th song has a duration of time[i] seconds.

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

Try coding it in LeetCode

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_pairs

Big(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.

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

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_pairs

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Space Complexity

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.