LeetCode 2020 Dec 8 Pairs of Songs With Total Durations Divisible by 60
Problem Statement: We have to find the number of pair of songs which can be combined to have the durations which are divisible by 60.
The question is Leetcode .
Input will be the array of songs will the time taken for each song to play.
Some Pre understandings
- We can understand this problem is similar to famous two sum problem which can be done in single iteration of for loop.
- We are also clear that we need to have the added pair like 59 minutes + 1 minute. This pair is same as 59 minutes + 121 minutes.
- We can store both 1 minute and 121 mintue in the second index of array or can be stored in HashMap for the Key 1.
Pseudo Code
- We need to initialize HashMap (values) with the capacity 60. i.e., our HashMap can hold from 0 to 60 keys and values.
- Then we have to iterate the songs time array one by one.
- First we have to get the value at that index. Then we can first find the modulo of 60 (remember 1 and 121 are same for us). So we will get a value, we can call it currentTime
- We have to find the diff of this obtained number from 60. We can call this value as diffToCheck
- We have to check whether this diff value is present in hashMap already or not. We will use the method getOrDefault so if we have the value we will return it else we can return 0.
- Next step is we have to insert the currentTime time into the HashMap so when we are getting same diff we can count it.
Java Code
public int numPairsDivisibleBy60(int[] time) {
int totalPairs =0;
if(time != null){
HashMap<Integer,Integer> values = new HashMap<Integer,Integer>(60);
for(int indexOFTimeArray =0 ; indexOFTimeArray < time.length; ++indexOFTimeArray){
int currentTime = time[indexOFTimeArray] %60;
int diffToCheck = (60 - currentTime) % 60;
if( values.containsKey(diffToCheck)){
totalPairs = totalPairs + values.getOrDefault(diffToCheck,0);
}
values.put(currentTime, 1+values.getOrDefault(currentTime,0));
}
}
return totalPairs;
}