1010. Pairs of Songs With Total Durations Divisible by 60 (Medium)

Brute force (TLE)

• We can find all the pairs from the time array which are divisible by 60
• TC: O(N^2)
• SC: O(1)

Hashing Solution

• t % 60 gets the remainder from 0 to 59.
• We count the occurrence of each remainders in a array/hashmap mp.
• we want to know that, for each t in time, how many x satisfy (t + x) % 60 = 0.
• The straight forward idea is to take x % 60 = 60 - (t % 60), which is valid for the most cases.
• But, if t % 60 = 0 then x % 60 should be 0 instead of 60.
• there are two solutions to avoid this situation,
  • x % 60 = (60 - t % 60) % 60,
  • x % 60 = (600 - t) % 60.
• TC: O(N), Single for loop
• SC: O(N), for the extra space to store the remainders.

Code

class Solution {
public:
    int numPairsDivisibleBy60(vector<int>& time)
    {
        vector<int> mp(60);
        int n = time.size(), ans = 0;
        for (int i = 0; i < n; i++) {
            int rem = time[i] % 60;
            ans += mp[(60 - rem) % 60];
            mp[rem]++;
        }
        return ans;
    }
};