Solution: Pairs of Songs With Total Durations Divisible by 60

Grokking Oracle Coding Interview

Ask Author

Back to course home

0% completed

Vote For New Content

Solution: Pairs of Songs With Total Durations Divisible by 60

Table of Contents

Contents are not accessible

Problem Statement

You are given a list of positive integer times, where times[i] represents the duration of i<sup>th</sup> song in seconds.

Return the number of unique song pairs for which their total duration in seconds is multiple of 60. In other words, find the number of indices i, j such that i < j with (times[i] + times[j]) % 60 == 0.

Examples

Example 1:

Input: times = [30, 20, 150, 100, 40, 110]
Expected Output: 3
Justification: The pairs of songs that can form a total duration divisible by 60 are (30, 150), (20, 100), and (20, 40). Each of these pairs sums up to a multiple of 60, hence the expected output is 3.

Example 2:

Input: times = [120, 180, 60]
Expected Output: 3
Justification: The sum of (120, 180), (120, 60), and (180, 60) are divisible by 60. So, the expected output is 3.

Example 3:

Input: times = [15, 225, 90, 60]
Expected Output: 1
Justification: The only pair of songs that can form a total duration divisible by 60 is (15, 225).

Solution

To solve this problem, we'll use a hash table to keep track of the frequencies of song durations modulo 60. The rationale behind this approach is that if the sum of two numbers is divisible by 60, then the sum of their remainders when divided by 60 should also be 0. This method is effective because it allows us to handle each duration independently and just focus on its contribution towards forming a valid pair, significantly simplifying the problem.

First, we iterate through the list of song durations, calculating each song's remainder when divided by 60 and updating the frequency of these remainders in our hash table. Then, for each duration, we look for complementary durations that can form a valid pair with it. This two-step process efficiently identifies all possible pairs without the need for direct comparison of each song duration with every other, thereby reducing computational complexity and increasing algorithm efficiency.

Step-by-Step Algorithm

Initialize a Frequency Array: Create an array named remainderFrequency with a size of 60 to store the frequency of the remainders when each song duration is divided by 60. This array is initialized with all elements set to 0.
Populate the Frequency Array: Iterate through each element in the input array times. For each song duration t in times, calculate the remainder of t divided by 60. Increment the value at the index of this remainder in the remainderFrequency array by 1. This step counts how many songs have durations that leave the same remainder when divided by 60.
Initialize a Count Variable: Initialize a variable count to 0. This variable will keep track of the total number of valid pairs of songs found.
Calculate Pairs for Special Cases: Calculate the number of valid pairs for songs that leave a remainder of 0 and for songs that leave a remainder of 30 when their durations are divided by 60. This is done because these remainders pair with themselves. Use the formula remainderFrequency[i] * (remainderFrequency[i] - 1) / 2 for i = 0 and i = 30, and add the results to count.
Calculate Pairs for Other Remainders: Iterate from i = 1 to i = 29. For each i, find the product of the frequency of songs with remainder i and the frequency of songs with remainder 60 - i. Add this product to count. This step finds and counts all valid pairs of songs where the sum of their durations' remainders equals 60.
Return the Total Count: After iterating through the remainderFrequency array and calculating all possible pairs, return the value of count. This value represents the total number of pairs of songs where the sum of their durations is divisible by 60.

Algorithm Walkthrough

Initialize remainderFrequency Array: Create an array of size 60, initialized with zeros.
Populate the Frequency Array:
- For 30, calculate 30 % 60 = 30. Increment remainderFrequency[30] to 1.
- For 20, calculate 20 % 60 = 20. Increment remainderFrequency[20] to 1.
- For 150, calculate 150 % 60 = 30. Increment remainderFrequency[30] to 2.
- For 100, calculate 100 % 60 = 40. Increment remainderFrequency[40] to 1.
- For 40, calculate 40 % 60 = 40. Increment remainderFrequency[40] to 2.
- For 110, calculate 110 % 60 = 50. Increment remainderFrequency[50] to 1.
- The final hashmap is {20: 1, 30: 2, 40: 2, 50: 1}.
Initialize count Variable: Set count to 0.
Calculate Pairs for Special Cases:
- For i = 0, there are no songs with a remainder of 0, so count remains 0.
- For i = 30, use the formula 2 * (2 - 1) / 2 = 1. Increment count by 1.
Calculate Pairs for Other Remainders:
- For i = 1 to 29, calculate pairs.
- For i = 20, add remainderFrequency[20] * remainderFrequency[40] = 1 * 2 = 2 in the count. count = 1 + 2 = 3
Return the Total Count: The final count is 3, indicating there are 3 valid pairs of songs where the sum of their durations is divisible by 60.

Code

Python3

. . . .

Complexity Analysis

Time Complexity

$O(n)$ : The algorithm iterates through the input array times once to populate the remainderFrequency array, where n is the number of elements in times. This operation takes linear time. Afterward, it iterates through the remainderFrequency array up to 30 times to calculate the number of valid pairs. Since this second iteration is a constant operation (does not depend on the input size n), the overall time complexity remains $O(n)$ .

Space Complexity

$O(1)$ : The space complexity is constant because the algorithm uses a fixed-size array remainderFrequency of size 60, regardless of the input size. Other variables used in the algorithm do not significantly affect the space usage.

.....

Like the course? Get enrolled and start learning!

Table of Contents

Contents are not accessible