The whole-minute dilemma is a challenge where the goal is to determine the number of pairs of songs whose combined durations are perfectly divisible by 60. This article will explore this algorithmic puzzle, discuss the problem, present a brute-force solution, and then delve into a more efficient approach. We will also implement code in C++, Java, and Python.
What is a Whole-minute dilemma Problem?
In the Whole Minute Dilemma problem, we are given a list of songs each represented by its duration in seconds. The task is to find the number of pairs of songs for which the sum of their durations is divisible by 60. Our goal is to determine the count of pairs (i, j) such that i < j and (time[i] + time[j]) % 60 = 0.
For example,
time = [30,20,150,100,40]
Output: 3
There exist three pairs whose sum of values is divisible by 60.
We can easily solve this programming problem using a simple Brute Force approach. In this approach, we must find all the possible pairs and check if their sum is divisible by 60. We have to use a nested loop to obtain all possible pairs for this.
Steps to solve the problem using this approach:
- Firstly we Initialize a variable count to keep track of whether any pairs are found.
- Now we Iterate over each song, denoted as time[i].
- Iterate over all subsequent songs, denoted as time[j], starting from j = i + 1.
- Check if (time[i] + time[j]) % 60 == 0.
- Now If true, we will increment the count variable.
The time complexity of this approach is O(n2), where n is the number of songs. As this approach checks all possible pairs, and for each valid pair found, increment the count variable.
Optimized Approach to Solve It
While the brute-force approach is a straightforward solution, it’s not the most efficient. Let’s explore a more optimized approach that uses the properties of modular arithmetic. We can manipulate this (time[i] + time[j]) % 60 = 0 to (time[i]%60+time[j]%60)%60 = 0 and use this to solve this problem. Let’s see how.
Steps to be followed in this approach:
- Firstly we will create an array remainderCount to count the occurrences of remainders when each song duration is divided by 60.
- remainder_count[i] will represent the count of songs whose duration has a remainder of i when divided by 60.
- remainder_count[i] will represent the count of songs whose duration has a remainder of i when divided by 60.
- Pairs with Remainder 0: We can form pairs with any other song having a remainder of 0. The count is given by (remainderCount[0] * remainderCount[0]-1 )/2 where remainderCount[0] is the count of songs with remainder 0
- Pairs with Remainder 30: For songs with a remainder of 30, the pair can be formed with any other song having a remainder of 30 The count of such pairs is given by (remainderCount[30] * remainderCount[30]-1 )/2 where remainderCount[30] is the count of songs with remainder 30
- For other remainders, we count pairs as remainderCount[i] * remainderCount[60 – i]
C++ Code
Here is the C++ program to solve the Whole Minute Dilemma problem:
#include<bits/stdc++.h>
using namespace std;
int countPairsDivisibleBy60(vector<int>& time) {
vector<int> remainderCount(60, 0);
int count = 0;
// Populate remainderCount vector
for (int t : time) {
remainderCount[t % 60]++;
}
// Count pairs with remainder 0
count += remainderCount[0] * (remainderCount[0] - 1) / 2;
// Count pairs with remainder 30
count += remainderCount[30] * (remainderCount[30] - 1) / 2;
// Count general case pairs
for (int i = 1; i < 30; ++i) {
count += remainderCount[i] * remainderCount[60 - i];
}
return count;
}
int main() {
vector<int> time = {30, 20, 150, 100, 40};
int result = countPairsDivisibleBy60(time);
cout << "Number of pairs divisible by 60: " << result << endl;
return 0;
}Java Code
Here is the Java program as well:
import java.util.HashMap;
public class Main {
public static int countPairsDivisibleBy60(int[] time) {
int[] remainderCount = new int[60];
int count = 0;
// Populate remainderCount array
for (int t : time) {
remainderCount[t % 60]++;
}
// Count pairs with remainder 0
count += remainderCount[0] * (remainderCount[0] - 1) / 2;
// Count pairs with remainder 30
count += remainderCount[30] * (remainderCount[30] - 1) / 2;
// Count general case pairs
for (int i = 1; i < 30; ++i) {
count += remainderCount[i] * remainderCount[60 - i];
}
return count;
}
public static void main(String[] args) {
int[] time = {30, 20, 150, 100, 40};
int result = countPairsDivisibleBy60(time);
System.out.println("Number of pairs divisible by 60: " + result);
}
}Python Code
Here is the Python solution for the Whole Minute Dilemma problem:
def count_pairs_divisible_by_60(time):
remainder_count = [0] * 60
count = 0
# Populate remainder_count list
for t in time:
remainder_count[t % 60] += 1
# Count pairs with remainder 0
count += remainder_count[0] * (remainder_count[0] - 1) // 2
# Count pairs with remainder 30
count += remainder_count[30] * (remainder_count[30] - 1) // 2
# Count general case pairs
for i in range(1, 30):
count += remainder_count[i] * remainder_count[60 - i]
return count
if __name__ == "__main__":
time = [30, 20, 150, 100, 40]
result = count_pairs_divisible_by_60(time)
print("Number of pairs divisible by 60:", result)Output:
Number of pairs divisible by 60: 3The time complexity of this approach is O(n), where n is the size of the time vector. As in this loop iterates through each element in the time vector once. The space complexity of this approach is O(1) as we are not using any extra space.
Comparing both of them, the brute force approach checks all possible pairs, and for each valid pair found, increment the count variable with O(n2) time complexity. In the optimized solution, we use a loop, which iterates through each element in the time vector once. This decreases the time complexity to O(n).
Conclusion
So, we have discussed 2 approaches, the first one is absolute brute force and the second one is an optimized approach in which we have used principles of modular arithmetic and the concept of remainders. Now you can easily crack the interview if the question is about whole minute dilemma problem. If you have some more problems, you might get expert assistance from our Python tutors online anytime anywhere.
