
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.
NOTES
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; } };