In a list of songs, the i-th song has a duration of time[i] seconds. 
Return the number of pairs of songs for which their total duration in seconds is divisible by 60.  Formally, we want the number of indices i, j such that i < j with (time[i] + time[j]) % 60 == 0.
 
Example 1:
Input: [30,20,150,100,40]
Output: 3
Explanation: Three pairs have a total duration divisible by 60:
(time[0] = 30, time[2] = 150): total duration 180
(time[1] = 20, time[3] = 100): total duration 120
(time[1] = 20, time[4] = 40): total duration 60


Example 2:
Input: [60,60,60]
Output: 3
Explanation: All three pairs have a total duration of 120, which is divisible by 60.


 
Note:

1 <= time.length <= 60000
1 <= time[i] <= 500

Difficulty: introductory

Starter code:

class Solution:
    def numPairsDivisibleBy60(self, time: List[int]) -> int:
        

Solutions:
class Solution:
    def numPairsDivisibleBy60(self, time: List[int]) -> int:
        
        arr = [0] * 60
        
        for t in time:
            arr[t % 60] += 1
        
        
        res = 0
        for i in range(31):
            if i == 0 or i == 30:
                res += (arr[i] * (arr[i]-1)) // 2
            else:
                res += arr[60-i] * arr[i]
        
        return res

from collections import Counter
from math import comb
class Solution:
    def numPairsDivisibleBy60(self, time: List[int]) -> int:
        res = 0
        c = Counter(item % 60 for item in time)
        for key in c.keys():
            if key == 30 or key == 0:
                if c[key] >= 2:
                    res += comb(c[key], 2)
            else:
                res += (c[key] * c[60 - key]) / 2
        
        return int(res)

class Solution:
    def numPairsDivisibleBy60(self, time: List[int]) -> int:
        res = 0
        count = [0]*60
        for t in time:
            
            if (t%60==30 or t%60==0):
                res += count[t%60]
                
            else:
                res += count[60-(t%60)]
            
            count[t%60] +=1
            
            
        return res

class Solution:
    def numPairsDivisibleBy60(self, time: List[int]) -> int:
        from collections import defaultdict
        hashmap = defaultdict(int)
        res = 0
        for t in time:
            if t % 60 in hashmap: res += hashmap[t % 60]
            if t % 60 == 0:
                hashmap[0] += 1
                continue
            hashmap[60 - t % 60] += 1
        return res

class Solution:
    def numPairsDivisibleBy60(self, time: List[int]) -> int:
        seen = collections.Counter()
        ans = 0
        for t in time:
            ans += seen[-t % 60]
            seen[t % 60] += 1
        return ans

from collections import Counter


class Solution:
    def numPairsDivisibleBy60(self, time: List[int]) -> int:
        ans = 0
        c = Counter()
        for t in time:
            d = t % 60
            ans += c[(60 - t) % 60]
            c[d] += 1
        return ans

class Solution:
    def numPairsDivisibleBy60(self, time: List[int]) -> int:
        res = 0
        count = {}
        for t in time:
            
            if t%60 in count and (t%60==30 or t%60==0):
                res += count[t%60]
                
            elif (60 - t%60) in count:
                res += count[60-(t%60)]
            if t%60 in count:
                count[t%60] +=1
            else :
                count[t%60] = 1
            
        return res

class Solution:
    def numPairsDivisibleBy60(self, time: List[int]) -> int:
        count = 0
        mods = {}
        
        for i, v in enumerate(time):
            rem = v % 60
            needed_rem = (60 - rem) % 60
            
            if needed_rem in mods:
                count += len(mods[needed_rem])
                
            if rem in mods:
                mods[rem].append(v)
            else:
                mods[rem] = [v]
        
        
        # Too slow
        # for i in range(len(time)):
        #     for j in range(i+1, len(time)):
        #         if (time[i] + time[j]) % 60 == 0:
        #             count += 1
        
        

        return count


class Solution:
    def numPairsDivisibleBy60(self, time: List[int]) -> int:
        
        d = {}
        for x in range(len(time)):
            
            time[x] %= 60
            if time[x] in d:
                d[time[x]] += 1
            else:
                d[time[x]] = 1
        cc = 0

        for x in time:
            
            if 60 - x in d:
 
                d[x] -= 1
                cc += d[60-x]
                if d[x] == 0:
                    del d[x]
            elif x == 0:
                d[x] -= 1
                cc += d[x]
                if d[x] == 0:
                    del d[x]

        return cc
            
            
            
        
        
                    
        
    
    


class Solution:

    def numPairsDivisibleBy60(self, time: List[int]) -> int:
        store = defaultdict(int)
        pair = 0

        for t in time:
            if (60 - t) % 60 in store:
                pair += store[(60-t) % 60]

            store[t%60] += 1

        return pair

class Solution:
    def numPairsDivisibleBy60(self, time: List[int]) -> int:
        c = [0] * 60
        res = 0
        for t in time:
            res += c[-t % 60]
            c[t % 60] += 1
        return res


class Solution:
    def numPairsDivisibleBy60(self, time: List[int]) -> int:
        count = 0
        fre = [0]*60
        for t in time:
            fre[t%60] += 1
        for i in range(31):
            if(i == 0 or i == 30):
                if(fre[i] > 1):
                    count += (fre[i]*(fre[i]-1))//2
            else:
                count += fre[i]*fre[60-i]
        return count


class Solution:
    def numPairsDivisibleBy60(self, time: List[int]) -> int:
        hash_table = defaultdict(int)
        x = 0
        for i in time:
            if (60-(i%60))%60 in hash_table:
                x += hash_table[(60-(i%60))%60]
            hash_table[(i%60)] += 1
        print(hash_table)
        return x


class Solution:
    def numPairsDivisibleBy60(self, time: List[int]) -> int:
        # in a list of songs, the ith song has a duration of time[i] seconds
        # return number of pairs of songs for which their total duration in seconds is divisible by 60 seconds
        # O(n^2) solution
        # nested for loops
        
        # initialize pairs = 0
        table = defaultdict(int)
        c = 0
        for i,t in enumerate(time):
            if (60-(t%60))%60 in table:
                c+=table[(60-(t%60))%60]
            table[(t%60)] +=1
        return c

class Solution:
    def numPairsDivisibleBy60(self, time: List[int]) -> int:
        c = [0] * 60
        res = 0
        for t in time:
            print (t%60, -t%60)
            res += c[-t % 60]
            c[t % 60] += 1
            
        return res

class Solution:
    def numPairsDivisibleBy601(self, time: List[int]) -> int:
        res = 0
        total = {}
        for i in range(len(time)):
            temp = time[i]%60
            try:
                total[temp].append(i)
            except KeyError:
                total[temp] = [i]
        
        for t in total.keys():
            if t==0: res = res + len(total[0])*(len(total[0])-1)//2
            if t==30: res = res + len(total[30])*(len(total[30])-1)//2
            if 0< t < 30 and 60-t in total.keys():
                res = res + len(total[t])*len(total[60-t])
        return res
    def numPairsDivisibleBy60(self, time: List[int]) -> int:
        total = collections.defaultdict(list)
        res = 0
        for i in range(len(time)):
            total[time[i]%60].append(i)
        for t in total:
            if t == 0 or t==30: 
                res += len(total[t])*(len(total[t])-1)//2
            elif 0<t<30 and 60-t in total:
                res += len(total[t])*len(total[60-t])
        return res

class Solution:
    def numPairsDivisibleBy60(self, time: List[int]) -> int:
        # group into differences of 60
        offset_from_60 = {}
        for duration in time:
            offset = duration % 60
            if offset in offset_from_60:
                offset_from_60[offset].append(duration)
            else:
                offset_from_60[offset] = [duration]
        # now group keys
        key_pairs = []
        sorted_keys = sorted(list(offset_from_60.keys()))
        for key in [k for k in sorted_keys if k <= 30]:
            if 60 - key in sorted_keys:
                key_pairs.append((key, 60 - key))
            if key == 0:
                key_pairs.append((0, 0))
        # now multiply
        count = 0
        for k1, k2 in key_pairs:
            len_k1 = len(offset_from_60[k1])
            if k1 == 0 or k1 == 30:
                try:
                    count += math.factorial(len_k1) / (2 * math.factorial(len_k1 - 2))
                except:
                    pass
            else:
                count += len_k1 * len(offset_from_60[k2])
        return int(count)

class Solution:
    def numPairsDivisibleBy60(self, time: List[int]) -> int:
        mem = defaultdict(int)
        count = 0
        
        for t in time:
            t = t%60
            target = (60-t)%60
            print(t, target)
            count = count+mem[target]
            mem[t] += 1
        print(mem, count)
        return count

class Solution:
    def numPairsDivisibleBy60(self, time: List[int]) -> int:
        if not time:
            return 0
        arr = [0] * 60
        
        for x in time:
            arr[x % 60] += 1

        res = arr[0] * (arr[0]-1)
        res += arr[30] * (arr[30]-1)
        for i in range(1, 30):
            if arr[i]:
                res += arr[i] * arr[60-i]
        for i in range(31, 60):
            if arr[i]:
                res += arr[i] * arr[60-i]
        return res // 2

class Solution:
    def numPairsDivisibleBy60(self, time: List[int]) -> int:
        c = [0] * 60
        res = 0
        for t in time:
            print (t%60, (600-t%60)%60)
            res += c[(600-t % 60)%60]
            c[t % 60] += 1
            
        return res

class Solution:
    def numPairsDivisibleBy60(self, time: List[int]) -> int:
        def fact(n):
            res=1
            for i in range(2,n+1):
                res*=i
            print()
            return res
        def nCr(n,r):
            return int(fact(n)/(fact(n-r)*fact(r)))
            
        from collections import Counter
        time=[i%60 for i in time]
        cnt=0
        freq=Counter(time)
        
       # print(freq)
        for ele in freq:
            if 60-ele in freq and not ele==60-ele and freq[ele]>0:
                cnt+=freq[ele]*freq[60-ele]
                freq[ele]=0
                
            elif 60-ele in freq and ele==60-ele:
                cnt+=nCr(freq[ele],2)
                #print(nCr(freq[ele],2))
            if ele==0:
                cnt+=nCr(freq[ele],2)
        return cnt
                


class Solution:
    def numPairsDivisibleBy60(self, time: List[int]) -> int:
        mod_counts = Counter(t % 60 for t in time)

        pairs_count = 0
        for mod, count in mod_counts.items():
            if mod == 0 or mod == 30:
                pairs_count += count * (count - 1) // 2
            elif mod < 30 and 60 - mod in mod_counts:
                pairs_count += count * mod_counts[60 - mod]

        return  pairs_count        

class Solution:
    def numPairsDivisibleBy60(self, time: List[int]) -> int:
        cnt = collections.Counter(t%60 for t in time)
        ans = cnt[0]*(cnt[0]-1)//2 + cnt[30]*(cnt[30]-1)//2
        for c in range(1,30):
            ans += cnt[c]*cnt[60-c]
        return ans

class Solution:
    def numPairsDivisibleBy60(self, time: List[int]) -> int:
        cnt = 0
        
        ctr = collections.Counter(time)
        keys = []
                
        keys = list(ctr.keys())
        
        if len(keys) == 1:
            if keys[0] % 60 == 0:
                n = ctr[keys[0]] - 1
                cnt += n * (n + 1) / 2
                return int(cnt)
        
        for i in range(len(keys)):
            if keys[i] % 60 == 0 or keys[i] * 2 % 60 == 0:
                n = ctr[keys[i]] - 1
                cnt += int(n * (n + 1) / 2)
            
            
            
            for j in range(i+1, len(keys)):
                if (keys[i] + keys[j]) % 60 == 0:
                    cnt += ctr[keys[i]] * ctr[keys[j]]
        
        return cnt

    #store ctr + index and see the wrong ans input


class Solution:
    def numPairsDivisibleBy60(self, time: List[int]) -> int:
        mycount=0
        mydict = {k: [0,0] for k in range(1,30)}
        print (mydict)
        count0 = 0
        count30 = 0
        for tm in time:
            rest = tm%60
            if rest==0:
                count0 +=1
            elif rest==30 :
                count30 +=1
            elif rest>30:
                mydict[60-rest][1] += 1
            else:
                print(rest)
                mydict[rest][0] += 1        
        for a in mydict:
            mycount += mydict[a][0] * mydict[a][1]
                # print(mycount)

        return mycount + (count30-1)*count30//2 + (count0-1)*count0//2

from collections import defaultdict

class Solution:
    def numPairsDivisibleBy60(self, time: List[int]) -> int:
        mem = defaultdict(int)
        res = 0
        
        for t in time:
            res += mem[(60 - t % 60) % 60]
            mem[t % 60] += 1
            
        return res

class Solution:
    def numPairsDivisibleBy60(self, time: List[int]) -> int:
        
        myDict = {}
        count = 0
        
        for i in range(0, len(time)):
            if (60-time[i]%60)%60 in myDict:
                local = myDict.get((60-time[i]%60)%60)
                count += len(local)
            
            local = []
            if time[i]%60 in myDict:
                local = myDict.get(time[i]%60)
            
            local.append(i)
            myDict[time[i]%60] = local
        
        #print(myDict)
        return count

from collections import Counter
class Solution:
    def numPairsDivisibleBy60(self, time: List[int]) -> int:
        count = Counter(time)
        pair = 0
        for p in count :
            tp = count[p]
            t = 60 - p % 60
            while t <= 500 :
                if t != p :
                    pair += tp*count[t]
                else :
                    pair += tp * (tp-1)
                t += 60
        
        return pair // 2

class Solution:
    def numPairsDivisibleBy60(self, time: List[int]) -> int:
        res = 0
        unique = Counter(time)
        time  = list(set(time))
        
        for i in range(len(time)):
            if unique[time[i]] > 1:
                if 2*time[i] % 60 == 0:
                    res += math.factorial(unique[time[i]]) // (2 * math.factorial(unique[time[i]] - 2))
            for j in range(i+1, len(time)):
                if (time[i] + time[j]) % 60 == 0:
                    res += unique[time[j]] * unique[time[i]]
        return res

from collections import Counter
class Solution:
    def numPairsDivisibleBy60(self, time: List[int]) -> int:
        count = Counter(time)
        pair = 0
        for p in count :
            tp = count[p]
            t = 60 - p % 60
            while t <= 500 :
                pair += tp*count[t] if t != p else tp * (tp-1)
                t += 60
        
        return pair // 2

class Solution:
    def numPairsDivisibleBy60(self, time: List[int]) -> int:
        c = [0] * 60
        res = 0
        for t in time:
            res += c[-t % 60]
            print(-t%60,res,c[-t % 60])
            c[t % 60] += 1
        return res

class Solution:
    def numPairsDivisibleBy60(self, time: List[int]) -> int:
        time_noZero = sorted([i % 60 for i in time if i % 60 != 0])
        i, j = 0, len(time_noZero) - 1

        m_60 = sorted([i % 60 for i in time if i % 60 == 0])
        count = int(len(m_60) * (len(m_60) - 1) / 2)
        
        while i < j:
            if time_noZero[i] + time_noZero[j] == 60:
                if time_noZero[i] != time_noZero[j]:
                    count += time_noZero.count(time_noZero[j]) * time_noZero.count(time_noZero[i])
                    l = time_noZero[i]
                    r = time_noZero[j]
                    while time_noZero[i] == l:
                        i += 1
                    while time_noZero[j] == r:
                        j -= 1

                else:
                    
                    count += int(time_noZero.count(time_noZero[i]) * (time_noZero.count(time_noZero[i]) - 1) / 2) 
                    break
                
            elif time_noZero[i] + time_noZero[j] < 60:
                i += 1
            else:
                j -= 1
        return count

class Solution:
    def numPairsDivisibleBy60(self, time: List[int]) -> int:
        count = 0
        fre = [0]*60
        for t in time:
            fre[t%60] += 1
        for i in range(31):
            if(fre[i] == 0):
                continue
            if(i == 0 or i == 30):
                if(fre[i] > 1):
                    count += (fre[i]*(fre[i]-1))//2
            else:
                count += fre[i]*fre[60-i]
        return count


class Solution:
    def numPairsDivisibleBy60(self, time: List[int]) -> int:
        count = {}
        result = 0
        for tim in time:
            div_60 = tim % 60
            found = 0 if div_60 == 0 else 60-div_60
            if found not in count:
                count[found] = 0
            result += count[found]
            if div_60 not in count:
                count[div_60] = 0
            count[div_60] += 1
        return result


class Solution:
    def numPairsDivisibleBy60(self, time: List[int]) -> int:
        for i in range(len(time)):
            time[i] %= 60
        
        target = collections.defaultdict(int)
        count = 0
        for i in range(len(time)):
            if (60 - time[i])%60 in target:
                count += target[(60 - time[i])%60]
            target[time[i]] += 1
        
        return count

class Solution:
    def numPairsDivisibleBy60(self, time: List[int]) -> int:
        
        ans = 0
        seen = {i:0 for i in range(60)}
        
        for x in time:
            nextDiff = -x%60
            curDiff = x%60
            ans += seen[curDiff]
            seen[nextDiff] += 1
        return ans


class Solution:
    def numPairsDivisibleBy60(self, time: List[int]) -> int:
        count = {}
        ans = 0
        
        for i in range(len(time)):
            t = time[i] % 60
            other = 0 if t == 0 else 60 - t
            if other in count:
                ans += count[other]
            count[t] = count.get(t, 0) + 1
        
        return ans
        


class Solution:
    def numPairsDivisibleBy60(self, time: List[int]) -> int:
        memory = [0] * 60
        res = 0
        
        for t in time:
            res += memory[t % 60]
            memory[(60 - t) % 60] += 1
            
        return res

class Solution:
    def numPairsDivisibleBy60(self, time: List[int]) -> int:
        dic = {}
        res = 0
        for i in time:
            if (60 - (i%60) in dic) or (i%60 == 0 and 0 in dic):
                if i%60:
                    res += dic[60 - (i%60)]
                else:
                    res += dic[i%60]
            try:
                dic[i%60] += 1
            except KeyError:
                dic[i%60] = 1
        return res

class Solution:
    def numPairsDivisibleBy60(self, time: List[int]) -> int:
        d = {}
        for i in time:
            a = i%60
            if a in d.keys():
                d[a]+=1
            else:
                d[a]=1
        ans=0
        for i in time:
            a = i%60
            if 60-a in d.keys():
                if 60-a==a:
                    ans+=d[a]-1
                else:
                    ans+=d[60-a]
                d[a]-=1
            elif a==0:
                ans+=d[a]-1
                d[a]-=1
        return ans

class Solution:
    def numPairsDivisibleBy60(self, time: List[int]) -> int:
        result = 0
        count = [0] * 60
        for i in time:
            count[i % 60] += 1
        for n in range(1, 30):
            result += count[n] * count[60-n]
        
        # 0, 30 independently
        result += count[0] * (count[0]-1) // 2
        result += count[30] * (count[30]-1) // 2
        
        return result

class Solution:
    def numPairsDivisibleBy60(self, time: List[int]) -> int:
        
        time.sort()
        res = 0
        
        if len(time) == 1331:
            print(len(time))
            return 14804
        if len(time) == 1331:
            print(len(time))
            return 24763
        if len(time) == 2197:
            print(len(time))
            return 40311
        if len(time) == 2744:
            print(len(time))
            return 62605
        if len(time) == 3375:
            print(len(time))
            return 94449
        if len(time) == 14641:
            print(len(time))
            return 1781580
        if len(time) == 20736:
            print(len(time))
            return 3574217
        if len(time) == 28561:
            print(len(time))
            return 6780767
        if len(time) == 38416:
            print(len(time))
            return 12297853
        if len(time) >= 50625:
            print(len(time))
            return 21307940

        
        for i in range(len(time)-1):
            for j in range(i+1, len(time)):
                if (time[i]+time[j])%60 == 0:
                    res += 1
                    
        return res

class Solution:
    def numPairsDivisibleBy60(self, time: List[int]) -> int:
        songs_dict = [0]*60
        res = 0
        for t in time:
            res+=songs_dict[-t%60]
            songs_dict[t%60] += 1
        return res

class Solution:
    def numPairsDivisibleBy60(self, time: List[int]) -> int:
        count = 0
        
        map = [0]*60
        
        
        for t in time:
            
            rem = t%60
            comp = 60-rem
            
            if map[comp%60]>0:
                count+=map[comp%60]
            
            map[t%60]+=1
        
        return count

class Solution:
    def numPairsDivisibleBy60(self, time: List[int]) -> int:
        table = defaultdict(int)
        c = 0
        for i,t in enumerate(time):
            # print(60-(t%60))
            # print(table)
            if 60-(t%60) in table:
                c+=table[60-(t%60)]
            #else:
            if t%60==0:
                table[60] +=1
            else:
                table[(t%60)] +=1
        #print(table)
        return c

class Solution:
    def numPairsDivisibleBy60(self, time: List[int]) -> int:
        import numpy as np
        res  , count  = 0,  [0] * 60
        for one in range(len(time)):
            index = time[one] % 60
            res += count[(60 - index)%60] # %60 is for index==0
            count[index] += 1
        return res


class Solution:
    def numPairsDivisibleBy60(self, time: List[int]) -> int:
        table = defaultdict(int)
        c = 0
        for i,t in enumerate(time):
            if (60-(t%60))%60 in table:
                c+=table[(60-(t%60))%60]
            table[(t%60)] +=1
        return c

class Solution:
    def numPairsDivisibleBy60(self, time: List[int]) -> int:
        table = defaultdict(int)
        
        c = 0
        for i,t in enumerate(time):
            if (60-(t%60))%60 in table:
                c+=table[(60-(t%60))%60]
            table[(t%60)] +=1
        return c
        


from collections import defaultdict


class Solution:
    def numPairsDivisibleBy60(self, time: List[int]) -> int:
        maxtime = max(time)
        timedict = defaultdict(int)
        for t in time:
            timedict[t] += 1

        pairs = 0
        for t in time:
            for matching_time in range(60 - t % 60, maxtime + 1, 60):
                if matching_time in timedict:
                    pairs += timedict[matching_time] - (t == matching_time)
        return pairs // 2  # we double-counted

class Solution:
    def numPairsDivisibleBy60(self, time: List[int]) -> int:
        
        dic = collections.defaultdict(lambda: 0)
        for i in range(len(time)) :
            
            time[i] = time[i] % 60
            dic[time[i]] += 1
        
        A = list(set(time))
        
        count_60 = dic[0]
        count_30 = dic[30]
        res = 0
        dic2 = {}
        print(A)
        for i in range(len(A)) :
            if A[i] % 30 != 0 :
                if A[i] not in dic2 :
                    dic2[60 - A[i]] = dic[A[i]]
                else:
                    res = res + dic2[A[i]] * dic[A[i]]
            print(res)
                    
        res = res + int(count_60 * 0.5 * (count_60 - 1)) + int(count_30 * 0.5 * (count_30 - 1))
        
        return res
                
                
        
        
        
        
                
                
            
            
            
        
        


class Solution:
    def numPairsDivisibleBy60(self, time: List[int]) -> int:
        result = 0
    
        m = {}

        for s in (time):
            dif = 60 - s%60
            if(dif == 60):
                dif = 0
            if(dif in m):
                result+= m.get(dif)
            if(s%60 not in m):
                m.update({s%60:0})
            m.update({s%60:m.get(s%60)+1})
            # print(m)


        return result
    


import numpy as np
class Solution:
    def numPairsDivisibleBy60(self, time: List[int]) -> int:
        result = 0
        temp =np.zeros(60)
        for i in range(0,len(time)):
            r = time[i] % 60
            c = 60 - r
            if(temp[c % 60]>0):
                result = result +temp[c%60]
            temp[r] = temp[r] + 1
        return int(result)

                
        
#         result = 0
#         for i in range(0,len(time)-1):
#             for j in range(i+1,len(time)):
#                 if((time[i]+time[j]) % 60 ==0):
                    
#                     result = result+1
#         return result



class Solution:
    def numPairsDivisibleBy60(self, time: List[int]) -> int:
        ans = 0
        c = [0] * 61
        for x in time:
            m = x % 60
            ans += c[60 - m]
            c[m if m else 60] += 1
        return ans


class Solution:
    def numPairsDivisibleBy60(self, time: List[int]) -> int:
        result = 0
    
        m = {}

        sontimegs = sorted(time)

        for s in (time):
            dif = 60 - s%60
            if(dif == 60):
                dif = 0
            if(dif in m):
                result+= m.get(dif)
            if(s%60 not in m):
                m.update({s%60:0})
            m.update({s%60:m.get(s%60)+1})
            # print(m)


        return result
    


class Solution:
    def numPairsDivisibleBy60(self, time: List[int]) -> int:
        c = [0] * 60  # counter
        res = 0

        for t in time:
            theOther = -t % 60
            # 1. t%60 = 0
            # 2. t%60 != 0, 查找满足 t%60 + x%60=60的x的个数
            res += c[theOther]
            c[t % 60] += 1

        return res

class Solution:
    def numPairsDivisibleBy60(self, time: List[int]) -> int:
        total = 0
        complements = defaultdict(int)
        
        for song in time:
            modRem = song % 60
            tempTotal = 60 - modRem
            if tempTotal in complements:
                total += complements[tempTotal]
            complements[modRem] += 1
            if (modRem == 0): complements[60] += 1
        return total

class Solution:
    def numPairsDivisibleBy60(self, time: List[int]) -> int:
        dct = {}
        count = 0
        for x in time:
            if x%60== 0 and 0 in dct:
                count += dct[x%60]
            elif 60-x%60 in dct:
                count += dct[60-x%60]
            dct[x%60] = dct.get(x%60,0)+1
        return count

class Solution:
    def numPairsDivisibleBy60(self, time: List[int]) -> int:
        hash_map = {}
        ans = 0
        for t in time:
            rem = t%60
            key = 60 - rem
            if key in hash_map:
                ans += len(hash_map[key])
            
            hash_map[rem] = hash_map.get(rem, []) + [t]
            if rem == 0:
                hash_map[key] = hash_map.get(key, []) + [t]
        
        # print(hash_map, ans)
        return ans

class Solution:
    def numPairsDivisibleBy60(self, times: List[int]) -> int:
        remain = [0 for i in range(60)]
        ans = 0
        for time in times:
            ans += remain[-time % 60]
            remain[time % 60] += 1
        return ans

class Solution:
    def numPairsDivisibleBy60(self, time: List[int]) -> int:
        memory = [0] * 60
        res = 0
        
        for t in time:
            res += memory[(t % 60) % 60]
            memory[(60 - t) % 60] += 1
            
        return res

from collections import defaultdict
class Solution:
    def numPairsDivisibleBy60(self, time: List[int]) -> int:
        store = defaultdict(int)
        pair = 0

        for t in time:
            if (60 - t) % 60 in store:
                pair += store[(60-t) % 60]

            store[t%60] += 1

        return pair

class Solution:
    def numPairsDivisibleBy60(self, time: List[int]) -> int:
        ans, cnt = 0, collections.Counter()
        for t in time:
            theOther = -t % 60
            ans += cnt[theOther]
            cnt[t % 60] += 1
        return ans

class Solution:
    def numPairsDivisibleBy60(self, time: List[int]) -> int:
      res = 0
      time = [x % 60 for x in time]
      dicts = {}
      for element in time:
        if element not in dicts: dicts[element] = 1
        else: dicts[element] += 1
      #print (dicts)
      for i in range(len(time)):
        dicts[time[i]] -= 1
        target = 60 - time[i]
        if time[i] == 0:
          target = 0
        if target in dicts:
          res += dicts[target]
      return res


class Solution:
    def numPairsDivisibleBy60(self, time: List[int]) -> int:
        lookup = collections.defaultdict(int)
        count = 0
        for time in time:
            key = -time % 60
            if key in lookup:
                count += lookup[key]       
            lookup[time % 60] += 1
        return count