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

Source: leetcode | Difficulty: EASY
Tags: Data structures

Mathematics

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:
		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]
		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:
		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:
		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 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:
		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]
		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))
		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:

		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)
		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)
			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


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]
		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
		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


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:
		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]
		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:
		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:
		import numpy as np
		(res, count) = (0, [0] * 60)
		for one in range(len(time)):
			index = time[one] % 60
			res += count[(60 - index) % 60]
			count[index] += 1
		return res


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


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


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:
		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]
		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:
		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
		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