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