Pairs of Songs With Total Durations Divisible by 60 Solution In C++/Java/Python/JS
Problem Description
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.
Examples:
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
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 *104
- 1 <= time[i] <= 500
The problem requires counting pairs of songs whose total duration is divisible by 60. The key insight is to use the remainder when each song length is divided by 60. For each duration, we check how many previously seen durations have a complementary remainder (i.e., (60 - remainder) % 60).
Brute Force Approach
Intuition
To solve this problem, we need to find pairs of songs whose total duration is divisible by 60. A straightforward way to approach this is to consider every possible pair of songs and check if their sum meets the condition. Since we are given an array of durations, a beginner might first think about iterating through all possible pairs to check their sum, which is exactly what this brute force approach does.
The code iterates through each song duration using a nested loop. The outer loop selects a song at index i, and the inner loop picks another song at index j (where j > i). For each pair, we check whether their sum is divisible by 60 using the modulus operator ((time[i] + time[j]) % 60 == 0). If the condition holds true, we increment a counter to keep track of valid pairs.
This approach is intuitive because it directly follows the problem statement by checking all possible pairs. However, since it involves two nested loops, the time complexity is O(N²), meaning it becomes inefficient for large input sizes. A more optimized solution would involve using a frequency array or hashmap to count remainders, allowing us to determine valid pairs more efficiently.
Despite its inefficiency, this brute force method is a great starting point for understanding the problem. It helps build the intuition that each song contributes a remainder when divided by 60, which can later be leveraged in optimized solutions. For beginners, this step-by-step checking approach provides a clear way to grasp the core idea before moving on to more efficient implementations.
Approach
Step 1: Initialize Variables
- We start by defining a class Solution with a public method numPairsDivisibleBy60.
- Inside the function, we declare an integer variable count and initialize it to 0. This variable will keep track of the number of valid song pairs whose total duration is divisible by 60.
Step 2: Iterate Over All Possible Pairs
- We use two nested loops to go through all possible pairs (i, j), ensuring that i < j
- The outer loop runs from i = 0 to i = time.size() - 1, selecting each song one by one.
- The inner loop runs from j = i + 1 to j = time.size() - 1, selecting the second song to form a pair with the song at index i.
Step 3: Check the Divisibility Condition
- Inside the nested loop, we compute the sum of time[i] and time[j].
- We then check whether this sum is divisible by 60 using the modulo operator:
(time[i] + time[j]) % 60 == 0 - If this condition is met, it means that the pair (i, j) forms a valid pair, so we increment the count variable.
Step 4: Return the Final Result
- After both loops have finished iterating through all possible pairs, count holds the total number of valid song pairs.
- Finally, we return count as the output.
Pairs of Songs With Total Durations Divisible by 60 Dry run - BruteForce
Input: time = [30,20,150,100,40]
Step 1: Initialize count = 0
Step 2: Start iterating through all pairs (i, j) where i < j
i = 0, time[i] = 30
- j = 1, time[j] = 20 → 30 + 20 = 50 (not divisible by 60)
- j = 2, time[j] = 150 → 30 + 150 = 180 (divisible by 60) → count = 1
- j = 3, time[j] = 100 → 30 + 100 = 130 (not divisible by 60)
- j = 4, time[j] = 40 → 30 + 40 = 70 (not divisible by 60)
i = 1, time[i] = 20
- j = 2, time[j] = 150 → 20 + 150 = 170 (not divisible by 60)
- j = 3, time[j] = 100 → 20 + 100 = 120 (divisible by 60) → count = 2
- j = 4, time[j] = 40 → 20 + 40 = 60 (divisible by 60) → count = 3
i = 2, time[i] = 150
- j = 3, time[j] = 100 → 150 + 100 = 250 (not divisible by 60)
- j = 4, time[j] = 40 → 150 + 40 = 190 (not divisible by 60)
i = 3, time[i] = 100
- j = 4, time[j] = 40 → 100 + 40 = 140 (not divisible by 60)
Step 3: The final count is 3, so the function returns 3.
Pairs of Songs With Total Durations Divisible by 60 Code for All Languages - BruteForce
C++
class Solution {
public:
int numPairsDivisibleBy60(vector<int>& time) {
int count = 0;
// Iterate over all pairs (i, j) where i < j
for (int i = 0; i < time.size(); i++) {
for (int j = i + 1; j < time.size(); j++) {
// Check if the sum of time[i] and time[j] is divisible by 60
if ((time[i] + time[j]) % 60 == 0) {
count++;
}
}
}
return count;
}
};Pairs of Songs With Total Durations Divisible by 60 code in Java - BruteForce
class Solution {
public int numPairsDivisibleBy60(int[] time) {
int count = 0;
// Iterate over all pairs (i, j) where i < j
for (int i = 0; i < time.length; i++) {
for (int j = i + 1; j < time.length; j++) {
// Check if the sum of time[i] and time[j] is divisible by 60
if ((time[i] + time[j]) % 60 == 0) {
count++;
}
}
}
return count;
}
}Pairs of Songs With Total Durations Divisible by 60 code in Python - BruteForce
class Solution:
def numPairsDivisibleBy60(self, time: List[int]) -> int:
count = 0
# Iterate over all pairs (i, j) where i < j
for i in range(len(time)):
for j in range(i + 1, len(time)):
# Check if the sum of time[i] and time[j] is divisible by 60
if (time[i] + time[j]) % 60 == 0:
count += 1
return countPairs of Songs With Total Durations Divisible by 60 code in Javascript - BruteForce
class Solution {
numPairsDivisibleBy60(time) {
let count = 0;
// Iterate over all pairs (i, j) where i < j
for (let i = 0; i < time.length; i++) {
for (let j = i + 1; j < time.length; j++) {
// Check if the sum of time[i] and time[j] is divisible by 60
if ((time[i] + time[j]) % 60 === 0) {
count++;
}
}
}
return count;
}
}Time Complexity: O(n2)
The given solution uses a brute-force approach, iterating over all possible pairs (i, j) where i < j.
The outer loop runs n times (n = time.size()).
Thus, the total time complexity is O(n²), making it inefficient for large n.
The inner loop runs from i + 1 to n - 1, leading to approximately n(n-1)/2 iterations.
Each iteration performs a constant-time modulo operation.
Space Complexity:O(1)
Auxiliary Space Complexity:
- The code only uses an integer variable count, which takes O(1) space.
- There are no extra data structures or dynamic allocations.
- Hence, auxiliary space complexity is O(1).
Total Space Complexity:
- The input vector time requires O(n) space.
- Since we don’t create any additional data structures beyond the input, the total space complexity remains O(n).
Optimal Approach
Intuition
Imagine you have a list of song durations, and you want to find pairs of songs where the total duration is a multiple of 60 seconds (like 60, 120, 180, etc.). Instead of checking all possible pairs, which would be too slow, we can use a smarter approach by focusing on remainders when dividing by 60.
Each song’s duration, when divided by 60, gives a remainder between 0 and 59. If two songs have remainders that add up to 60, they form a valid pair. For example, a song with a remainder of 40 can pair with a song that has a remainder of 20 (because 40 + 20 = 60). Similarly, a song with remainder 0 can pair with another song that also has remainder 0.
To efficiently count valid pairs, we use an array v of size 60 to store how many times each remainder has appeared. As we go through the list, for each song's remainder a, we check how many songs we’ve already seen that can pair with it. If a is 0, it pairs with previous songs with remainder 0. Otherwise, it pairs with songs that have remainder 60 - a. After checking, we update v[a] so future songs can pair with it.
By using this remainder-based approach, we avoid checking all pairs manually and solve the problem in a single pass through the list, making it much more efficient.
Approach
Step 1: Initialize a counter and a frequency array
Create a variable count to keep track of valid pairs. Also, initialize a vector v of size 60 with all elements set to 0. This array will store the count of occurrences of each remainder when dividing by 60.
Step 2: Iterate through the time array
Loop through each element in the time array. For each element, compute its remainder when divided by 60. This remainder helps in identifying which previously seen numbers can form a valid pair.
Step 3: Check for valid pairs
If the remainder is 0, it can form a pair with previously seen elements that also have a remainder of 0. Otherwise, check if there are any elements with a remainder of 60 - remainder, as their sum would be a multiple of 60. Add the count of such elements to count.
Step 4: Update the frequency array
After checking for valid pairs, update the frequency array v by increasing the count of the current remainder. This ensures that future elements can pair with it if needed.
Step 5: Return the total count
Once all elements have been processed, return the value of count, which represents the total number of valid pairs found.
Pairs of Songs With Total Durations Divisible by 60 Dry run - Optimised
time = [30, 20, 150, 100, 40]
Step 1: Initialize
count = 0
v = [0, 0, 0, ..., 0] (size 60, all values initialized to 0)
Step 2: Process each element
First element: 30
- Remainder = 30 % 60 = 30
- Complement needed = 60 - 30 = 30
- v[30] is 0, so no valid pairs yet
- Update v[30] to 1
Second element: 20
- Remainder = 20 % 60 = 20
- Complement needed = 60 - 20 = 40
- v[40] is 0, so no valid pairs yet
- Update v[20] to 1
Third element: 150
- Remainder = 150 % 60 = 30
- Complement needed = 60 - 30 = 30
- v[30] is 1, meaning one valid pair exists (30,150)
- Increase count by 1 (count = 1)
- Update v[30] to 2
Fourth element: 100
- Remainder = 100 % 60 = 40
- Complement needed = 60 - 40 = 20
- v[20] is 1, meaning one valid pair exists (20,100)
- Increase count by 1 (count = 2)
- Update v[40] to 1
Fifth element: 40
- Remainder = 40 % 60 = 40
- Complement needed = 60 - 40 = 20
- v[20] is 1, meaning one valid pair exists (20,40)
- Increase count by 1 (count = 3)
- Update v[40] to 2
Final Output: count = 3
The valid pairs are (30,150), (20,100), and (20,40), giving a total of 3 pairs whose sum is divisible by 60.
Pairs of Songs With Total Durations Divisible by 60 Code for All Languages - Optimised
C++
class Solution {
public:
int numPairsDivisibleBy60(vector<int>& time) {
// Initialize counter to store the number of valid pairs
int count = 0;
// Create a frequency array to store occurrences of remainders
vector<int> v(60, 0);
// Iterate through each element in the time array
for (int t : time) {
int remainder = t % 60;
// If remainder is 0, add the count of previously seen 0 remainders
if (remainder == 0)
count += v[0];
else
// Otherwise, add the count of numbers with remainder (60 - remainder)
count += v[60 - remainder];
// Store the current remainder in the frequency array
v[remainder]++;
}
// Return the final count of valid pairs
return count;
}
};Pairs of Songs With Total Durations Divisible by 60 Code in Java - Optimised
class Solution {
public int numPairsDivisibleBy60(int[] time) {
// Initialize counter to store the number of valid pairs
int count = 0;
// Create a frequency array to store occurrences of remainders
int[] v = new int[60];
// Iterate through each element in the time array
for (int t : time) {
int remainder = t % 60;
// If remainder is 0, add the count of previously seen 0 remainders
if (remainder == 0)
count += v[0];
else
// Otherwise, add the count of numbers with remainder (60 - remainder)
count += v[60 - remainder];
// Store the current remainder in the frequency array
v[remainder]++;
}
// Return the final count of valid pairs
return count;
}
}
Pairs of Songs With Total Durations Divisible by 60 Code in Python - Optimised
class Solution:
def numPairsDivisibleBy60(self, time: List[int]) -> int:
# Initialize counter to store the number of valid pairs
count = 0
# Create a frequency array to store occurrences of remainders
v = [0] * 60
# Iterate through each element in the time array
for t in time:
remainder = t % 60
# If remainder is 0, add the count of previously seen 0 remainders
if remainder == 0:
count += v[0]
else:
# Otherwise, add the count of numbers with remainder (60 - remainder)
count += v[60 - remainder]
# Store the current remainder in the frequency array
v[remainder] += 1
# Return the final count of valid pairs
return count
Pairs of Songs With Total Durations Divisible by 60 Code in Javascript - Optimised
class Solution {
numPairsDivisibleBy60(time) {
// Initialize counter to store the number of valid pairs
let count = 0;
// Create a frequency array to store occurrences of remainders
let v = new Array(60).fill(0);
// Iterate through each element in the time array
for (let t of time) {
let remainder = t % 60;
// If remainder is 0, add the count of previously seen 0 remainders
if (remainder === 0)
count += v[0];
else
// Otherwise, add the count of numbers with remainder (60 - remainder)
count += v[60 - remainder];
// Store the current remainder in the frequency array
v[remainder]++;
}
// Return the final count of valid pairs
return count;
}
}
Time Complexity: O(N)
- The function iterates through the time array exactly once, performing a constant number of operations for each element.
- Each lookup and update operation in the frequency array (v) takes O(1) time.
- Since we traverse the array only once, the overall time complexity is O(N), where N is the size of the time array.
Space Complexity: O(1)
Auxiliary Space Complexity (Extra space used apart from input)
- The frequency array v of size 60 is used to store remainder counts.
- Since v has a fixed size (60), it takes O(60) = O(1) space, which is constant.
- Apart from this, only a few integer variables (count, remainder, etc.) are used, which also contribute to O(1)space.
Total Space Complexity
- The input array time is given as input and is not modified, so it does not contribute to additional space usage.
- The frequency array v takes O(1) space.
- The total space complexity remains O(N) + O(1) ≈ O(N) if we consider the input array as part of the total space usage.
- If we only consider extra space (auxiliary space), it is O(1).
Learning Tip
Now we have successfully tackled this problem, let's try these similar problems.
You are given a 0-indexed array nums consisting of positive integers, representing targets on a number line. You are also given an integer space.
You have a machine which can destroy targets. Seeding the machine with some nums[i] allows it to destroy all targets with values that can be represented as nums[i] + c * space, where c is any non-negative integer. You want to destroy the maximum number of targets in nums.
Return the minimum value of nums[i] you can seed the machine with to destroy the maximum number of targets.
Given an integer array hours representing times in hours, return an integer denoting the number of pairs i, j where i < j and hours[i] + hours[j] forms a complete day.
A complete day is defined as a time duration that is an exactmultiple of 24 hours.
For example, 1 day is 24 hours, 2 days is 48 hours, 3 days is 72 hours, and so on