## Pairs of songs with total durations divisible by 60 | Leetcode #1010

This video explains a very important mathematical logic problem which applies the concept of remainder. I have explained how to find pairs of songs with total durations divisible by 60 starting from the brute force approach. I have also given observations and intuition for optimizing using remainder concept from mathematics. I have shown the first solution using brute force then i have shown optimal solution using hashmap. I have shown another optimal solution using array which uses idea of hashmap.This is the third method.

## CODE

```//Optimal Solution
class Solution {
public:
int numPairsDivisibleBy60(vector<int>& time) {
vector<int> rem(60);
for(int ele: time)
rem[ele%60]+=1;

int count=0;
count+=((rem[0]-1)*rem[0])/2;
count+=((rem[30]-1)*rem[30])/2;
for(int i=1;i<=29;++i)
count+=rem[i]*rem[60-i];

return count;
}
};

//Map solution
class Solution {
public:
int numPairsDivisibleBy60(vector<int>& time) {
unordered_map<int,int> m;   //Key->Remainder...Value->Frequency
for(int i=0;i<time.size();++i) {
time[i] %=60;
m[time[i]] +=1;
}

int count = 0;
for(auto it:m) {
if(it.first==0 or it.first==30)
count+=((it.second-1)*(it.second))/2;
else if(it.first<30 and m.count(60-it.first))
count+=(m[it.first]*m[60-it.first]);
}
return count;
}
};
```