Given an array of integers arr of even length n and an integer k.
We want to divide the array into exactly n / 2 pairs such that the sum of each pair is divisible by k.
Return True If you can find a way to do that or False otherwise.
 
Example 1:
Input: arr = [1,2,3,4,5,10,6,7,8,9], k = 5
Output: true
Explanation: Pairs are (1,9),(2,8),(3,7),(4,6) and (5,10).

Example 2:
Input: arr = [1,2,3,4,5,6], k = 7
Output: true
Explanation: Pairs are (1,6),(2,5) and(3,4).

Example 3:
Input: arr = [1,2,3,4,5,6], k = 10
Output: false
Explanation: You can try all possible pairs to see that there is no way to divide arr into 3 pairs each with sum divisible by 10.

Example 4:
Input: arr = [-10,10], k = 2
Output: true

Example 5:
Input: arr = [-1,1,-2,2,-3,3,-4,4], k = 3
Output: true

 
Constraints:

arr.length == n
1 <= n <= 10^5
n is even.
-10^9 <= arr[i] <= 10^9
1 <= k <= 10^5

Source: leetcode | Difficulty: MEDIUM
Tags: Data structures

Mathematics

Starter code: class Solution:
    def canArrange(self, arr: List[int], k: int) -> bool:
        

Solutions:
class Solution:

	def canArrange(self, arr: List[int], k: int) -> bool:
		freq = [0] * k
		for n in arr:
			freq[n % k] += 1
		if freq[0] % 2:
			return False
		for i in range(1, k // 2 + 1):
			if freq[i] != freq[k - i]:
				return False
		if k % 2 is 0:
			if freq[k // 2] % 2:
				return False
		return True


class Solution:

	def canArrange(self, arr, k):
		rem = [0] * k
		for a in arr:
			rem[a % k] += 1
		if rem[0] % 2 != 0:
			return False
		for i in range(1, (k - 1) // 2 + 1):
			if rem[k - i] != rem[i]:
				return False
		return True


class Solution:

	def canArrange(self, arr: List[int], k: int) -> bool:
		if len(arr) == 1:
			return False
		arr = collections.Counter([i % k for i in arr])
		if arr[0] % 2 == 1:
			return False
		i = 1
		j = k - 1
		while i <= j:
			if i == j:
				if arr[i] % 2 == 1:
					return False
			if arr[i] != arr[j]:
				return False
			i += 1
			j -= 1
		return True


class Solution:

	def canArrange(self, arr: List[int], k: int) -> bool:
		if len(arr) % 2 != 0:
			return False
		import collections
		ans = []
		lookup = collections.defaultdict(list)
		for (i, num) in enumerate(arr):
			if num % k in lookup:
				ans.append((arr[lookup[num % k].pop(0)], num))
				if lookup[num % k] == []:
					del lookup[num % k]
				continue
			if num % k == 0:
				lookup[0].append(i)
			else:
				lookup[k - num % k].append(i)
		return len(ans) == len(arr) // 2


class Solution:

	def canArrange(self, A: List[int], k: int) -> bool:
		A.sort(key=lambda x: x % k, reverse=True)
		(i, n) = (1, len(A))
		while i < len(A) and A[-i] % k == 0:
			if A[-i - 1] % k:
				return False
			else:
				i += 2
		if i < len(A):
			j = 0
			i0 = i
			while A[-i] % k and j < (n - i0 + 1) // 2:
				if (A[-i] + A[j]) % k:
					return False
				i += 1
				j += 1
		return True


class Solution:

	def canArrange(self, arr: List[int], k: int) -> bool:
		recDict = {}
		for i in range(0, k):
			recDict[i] = 0
		for i in arr:
			recDict[i % k] += 1
		for i in range(1, k):
			if recDict[i] != recDict[k - i]:
				return False
		if recDict[0] % 2 != 0:
			return False
		return True


from collections import Counter

class Solution:

	def canArrange(self, arr: List[int], k: int) -> bool:
		li = collections.Counter([x % k for x in arr])
		print(li)
		for i in li:
			if i == 0 or li[i] == 0:
				continue
			if li[k - i] != li[i]:
				return False
		if li[0] % 2 == 0:
			return True
		else:
			return False


class Solution:

	def canArrange(self, arr: List[int], k: int) -> bool:
		freq = collections.Counter(map(lambda x: x % k, arr))
		return not any((val % 2 if not key else val != freq[k - key] for (key, val) in freq.items()))


class Solution:

	def canArrange(self, arr: List[int], k: int) -> bool:
		cnt = [0] * k
		for a in arr:
			a %= k
			remainder = (k - a) % k
			if cnt[remainder] > 0:
				cnt[remainder] -= 1
			else:
				cnt[a] += 1
		return all((c == 0 for c in cnt))


class Solution:

	def canArrange(self, arr: List[int], k: int) -> bool:
		m = {i: 0 for i in range(k)}
		for a in arr:
			m[a % k] += 1
		for i in range(k):
			if i == 0:
				if m[i] % 2 != 0:
					return False
			elif m[i] != m[k - i]:
				return False
		return True


class Solution:

	def canArrange(self, arr: List[int], k: int) -> bool:
		d = collections.Counter()
		for e in arr:
			t = e % k
			d[t] += 1
		key = d.keys()
		print(d)
		for e in key:
			if e == 0:
				continue
			if d[e] != d[k - e]:
				return False
			elif e == k // 2 and k % 2 == 0 and (d[e] % 2 != 0):
				return False
		return True


class Solution:

	def canArrange(self, arr: List[int], k: int) -> bool:
		c = collections.Counter([i % k for i in arr])
		for j in c:
			if j == 0:
				if c[j] % 2 != 0:
					return False
			elif c[j] != c[k - j]:
				return False
		return True


from collections import Counter

class Solution:

	def canArrange(self, arr: List[int], k: int) -> bool:
		remainders = [0 for _ in range(k)]
		for number in arr:
			rem = number % k
			remainders[rem] += 1
		for i in range(k):
			if i == 0:
				if remainders[0] % 2 != 0:
					return False
				continue
			if remainders[i] != remainders[k - i]:
				return False
		return True


class Solution:

	def canArrange(self, arr: List[int], k: int) -> bool:
		nums = [i % k for i in arr]
		nums = [i for i in nums if i != 0]
		nums.sort()
		if len(nums) % 2 != 0:
			return False
		for i in range(len(nums) // 2):
			if (nums[i] + nums[-1 - i]) % k != 0:
				return False
		return True


import math

class Solution:

	def canArrange(self, arr: List[int], k: int) -> bool:
		moduloclasses = [0] * k
		for n in arr:
			moduloclasses[n % k] += 1
		if k % 2 == 0 and moduloclasses[k // 2] % 2 != 0:
			return False
		if moduloclasses[0] % 2 != 0:
			return False
		for i in range(1, math.ceil(k / 2)):
			if moduloclasses[i] != moduloclasses[k - i]:
				return False
		return True


class Solution:

	def canArrange(self, arr: List[int], k: int) -> bool:
		count = defaultdict(int)
		for x in arr:
			count[x % k] += 1
		if 0 in count:
			if count[0] % 2:
				return False
			else:
				count.pop(0)
		if k % 2 == 0 and k // 2 in count:
			if count[k // 2] % 2:
				return False
			else:
				count.pop(k // 2)
		while count:
			x = next(iter(count))
			if k - x in count:
				if count[k - x] == count[x]:
					count.pop(x)
					count.pop(k - x)
				else:
					return False
			else:
				return False
		return True


class Solution:

	def canArrange(self, arr: List[int], k: int) -> bool:
		d = [0] * k
		for i in range(len(arr)):
			d[arr[i] % k] += 1
		for i in range(len(d)):
			if i == 0:
				if d[i] % 2 != 0:
					return False
			elif d[i] != d[k - i]:
				return False
		return True


class Solution:

	def canArrange(self, arr: List[int], k: int) -> bool:
		arr_mod = [num % k for num in arr]
		arr_mod.sort()
		n = len(arr_mod)
		(left, right) = (0, n - 1)
		while left < n and arr_mod[left] == 0:
			left += 1
		if left % 2 != 0:
			return False
		while left < right:
			if arr_mod[left] + arr_mod[right] == k:
				left += 1
				right -= 1
			else:
				return False
		return True


from collections import defaultdict

class Solution:

	def canArrange(self, arr: List[int], k: int) -> bool:
		d = defaultdict(int)
		for a in arr:
			d[a % k] += 1
		res = True
		for i in range(1, (k + 1) // 2):
			print(i, k)
			if d[i] != d[k - i]:
				res = False
		if d[0] % 2 != 0:
			res = False
		if k % 2 == 0 and d[k // 2] % 2 != 0:
			res = False
		return res


from collections import defaultdict

class Solution:

	def canArrange(self, arr: List[int], k: int) -> bool:
		n: int = len(arr)
		mods = {ix: 0 for ix in range(k)}
		for val in arr:
			mods[val % k] += 1
		if mods[0] % 2 != 0:
			return False
		for mod in range(1, k):
			comp = k - mod
			if mods[comp] != mods[mod]:
				return False
		return True


class Solution:

	def canArrange(self, arr: List[int], k: int) -> bool:
		c = collections.Counter([a % k for a in arr])
		return all((c[i] == c[k - i] for i in range(1, k // 2 + 1))) and c[0] % 2 == 0


class Solution:

	def canArrange(self, arr: List[int], k: int) -> bool:
		dic = defaultdict(int)
		for u in arr:
			dic[u % k] += 1
		for i in range(1 + k // 2):
			if i == 0:
				if dic[0] % 2 != 0:
					return False
			elif dic[i] != dic[k - i]:
				return False
		return True


class Solution:

	def canArrange(self, arr: List[int], k: int) -> bool:
		if sum(arr) % k != 0:
			return False
		mod = defaultdict(int)
		for num in arr:
			if k - num % k in mod and mod[k - num % k] != 0:
				mod[k - num % k] -= 1
			else:
				mod[num % k] += 1
		print(mod)
		for (k, v) in mod.items():
			if k * v != 0:
				return False
		return True


class Solution:

	def canArrange(self, arr: List[int], k: int) -> bool:
		arr = [a % k for a in arr]
		arr.sort()
		arr = [a for a in arr if a != 0]
		if len(arr) % 2 == 1:
			return False
		(l, r) = (0, len(arr) - 1)
		while l < r:
			if arr[l] + arr[r] != k:
				return False
			r -= 1
			l += 1
		return True


class Solution:

	def canArrange(self, arr: List[int], k: int) -> bool:
		d = collections.defaultdict(int)
		for num in arr:
			d[num % k] += 1
		print(d)
		for i in range(k):
			if i in d:
				if i != k - i and k - i in d and (d[i] == d[k - i]):
					continue
				elif (i == 0 or i == k - i) and d[i] % 2 == 0:
					continue
				else:
					return False
		return True


class Solution:

	def canArrange(self, arr: List[int], k: int) -> bool:
		cnt = [0] * k
		for num in arr:
			cnt[num % k] += 1
		(i, j) = (1, k - 1)
		pairs = 0
		while i < j:
			if cnt[i] != cnt[j]:
				return False
			pairs += cnt[i]
			i += 1
			j -= 1
		if pairs > 0 and i == j:
			pairs += cnt[i] / 2
		pairs += cnt[0] / 2
		n = len(arr)
		return pairs == n // 2


class Solution:

	def canArrange(self, arr: List[int], k: int) -> bool:
		counts = Counter([x % k for x in arr])
		for key in counts:
			if key == 0 or key * 2 == k:
				if counts[key] % 2:
					return False
			elif counts[key] != counts[k - key]:
				return False
		return True


from collections import defaultdict

class Solution:

	def canArrange(self, arr: List[int], k: int) -> bool:
		counter = defaultdict(int)
		for n in arr:
			mod = n % k
			complement = (k - mod) % k
			if counter.get(complement, 0):
				counter[complement] -= 1
			else:
				counter[mod] += 1
		return all((v == 0 for v in counter.values()))


class Solution:

	def canArrange(self, arr: List[int], k: int) -> bool:
		if len(arr) % 2 == 1:
			return False
		mapping = defaultdict(int)
		count = 0
		for i in arr:
			key = k - i % k
			if key in mapping and mapping[key] >= 1:
				mapping[key] -= 1
				count += 1
			else:
				mapping[i % k or k] += 1
		if count == len(arr) // 2:
			return True
		return False


class Solution:

	def canArrange(self, arr: List[int], k: int) -> bool:
		cache = {}
		for x in arr:
			if x % k:
				comple = k - x % k
			else:
				comple = 0
			if cache.get(comple, 0):
				cache[comple] -= 1
			elif x % k in cache:
				cache[x % k] += 1
			else:
				cache[x % k] = 1
		return not sum(cache.values())


from collections import defaultdict

class Solution:

	def canArrange(self, arr: List[int], k: int) -> bool:
		if len(arr) % 2 == 1:
			return False
		lookup = defaultdict(int)
		count = 0
		for (idx, num) in enumerate(arr):
			key = k - num % k
			if key in lookup and lookup[key] >= 1:
				count += 1
				lookup[key] -= 1
			else:
				lookup[num % k or k] += 1
		return count == len(arr) // 2


class Solution:

	def canArrange(self, arr: List[int], k: int) -> bool:
		if len(arr) % 2 or sum(arr) % k:
			return False
		rems = [0] * k
		for a in arr:
			rems[a % k] += 1
		if rems[0] % 2:
			return False
		for i in range(1, k):
			if rems[i] != rems[k - i]:
				return False
		return True


class Solution:

	def canArrange(self, arr: List[int], k: int) -> bool:
		d = {}
		for num in arr:
			rem = num % k
			if rem in d:
				d[rem].append(num)
			else:
				d[rem] = [num]
		for i in d:
			if i == 0 or (k % 2 == 0 and i == k // 2):
				if len(d[i]) % 2 != 0:
					return False
			elif k - i in d:
				if len(d[i]) != len(d[k - i]):
					return False
			else:
				return False
		return True


class Solution:

	def canArrange(self, arr: List[int], k: int) -> bool:
		h = collections.defaultdict(int)
		invalid = 0
		for n in arr:
			mod = n % k
			completment = k - mod if mod > 0 else 0
			if h[completment] > 0:
				h[completment] -= 1
				if h[completment] == 0:
					invalid -= 1
			else:
				h[mod] += 1
				if h[mod] == 1:
					invalid += 1
		return invalid == 0


class Solution:

	def canArrange(self, A: List[int], k: int) -> bool:
		counter = Counter()
		for a in A:
			counter[a % k] += 1
		if counter[0] & 1 != 0:
			return False
		for i in range(1, k // 2 + 1):
			if counter[i] != counter[k - i]:
				return False
		return True


class Solution:

	def canArrange(self, arr: List[int], k: int) -> bool:
		from collections import defaultdict
		modulo = defaultdict(int)
		large_factor = 100000000.0
		for (i, v) in enumerate(arr):
			modulo[(v + large_factor * k) % k] += 1
		for (mod, cnt) in list(modulo.items()):
			if mod == 0 and cnt % 2 != 0:
				return False
			if modulo[(k - mod % k) % k] != cnt:
				return False
		return True


class Solution:

	def canArrange(self, arr: List[int], k: int) -> bool:
		counter = defaultdict(int)
		for ele in arr:
			ele %= k
			if counter[k - ele]:
				counter[k - ele] -= 1
			else:
				counter[ele] += 1
		if counter[0] % 2:
			return False
		counter[0] = 0
		for (k, v) in list(counter.items()):
			if v:
				return False
		return True


from collections import defaultdict

class Solution:

	def canArrange(self, arr: List[int], k: int) -> bool:
		n = len(arr)
		d = {i: 0 for i in range(k)}
		for ele in arr:
			d[ele % k] += 1
		for i in range(k):
			if d[0] % 2 != 0:
				return False
			elif i != 0 and d[i] != d[k - i]:
				return False
		return True


class Solution:

	def canArrange(self, arr: List[int], k: int) -> bool:
		if len(arr) % 2 != 0:
			raise Exception('Input array is of odd size!')
		mod_dict = {}
		for i in arr:
			mod = i % k
			pair_mod = (k - mod) % k
			if pair_mod in mod_dict:
				if mod_dict[pair_mod] == 1:
					del mod_dict[pair_mod]
				else:
					mod_dict[pair_mod] -= 1
			elif mod not in mod_dict:
				mod_dict[mod] = 1
			else:
				mod_dict[mod] += 1
		return len(mod_dict) == 0


from collections import Counter

class Solution:

	def canArrange(self, arr: List[int], k: int) -> bool:
		counter = Counter([num % k for num in arr])
		return all([counter[i] == counter[k - i] for i in range(1, k // 2 + 1)]) and counter[0] % 2 == 0


class Solution:

	def canArrange(self, arr: List[int], k: int) -> bool:
		bag = {}
		for i in arr:
			if i < 0:
				i += (-i // k + 1) * k
			r = i % k
			if r != 0:
				if k - r not in bag:
					if r not in bag:
						bag[r] = 0
					bag[r] += 1
				else:
					bag[k - r] -= 1
					if bag[k - r] == 0:
						del bag[k - r]
			elif 0 in bag:
				del bag[0]
			else:
				bag[0] = 1
		return len(bag) == 0


class Solution:

	def canArrange(self, arr: List[int], k: int) -> bool:
		freqs = [0] * k
		for n in arr:
			freqs[n % k] += 1
		for r in range(1, k // 2 + k % 2):
			if freqs[r] != freqs[k - r]:
				return False
		return not freqs[0] % 2


class Solution:

	def canArrange(self, arr: List[int], k: int) -> bool:
		remainder_cnt = {}
		for n in arr:
			if not n % k in remainder_cnt:
				remainder_cnt[n % k] = 0
			remainder_cnt[n % k] += 1
		for i in remainder_cnt:
			if i == 0 or i == k / 2:
				if remainder_cnt[i] % 2 != 0:
					return False
			elif not k - i in remainder_cnt or remainder_cnt[i] != remainder_cnt[k - i]:
				return False
		return True


class Solution:

	def canArrange(self, arr: List[int], k: int) -> bool:
		modFrequencies = {}
		for i in range(0, len(arr)):
			difference = arr[i] % k
			if difference not in modFrequencies:
				modFrequencies[difference] = 0
			modFrequencies[difference] += 1
		for mod in modFrequencies:
			if mod == 0:
				if modFrequencies[mod] % 2 == 1:
					return False
			elif k - mod not in modFrequencies or modFrequencies[mod] != modFrequencies[k - mod]:
				return False
		return True


from collections import defaultdict

class Solution:

	def canArrange(self, arr: List[int], k: int) -> bool:
		d = defaultdict(int)
		for num in arr:
			sgn = 1 if num >= 0 else -1
			num = sgn * (abs(num) % k)
			if num == 0:
				if d[0]:
					d[0] -= 1
					if d[0] == 0:
						del d[0]
				else:
					d[0] += 1
			elif -num in d and d[-num]:
				d[-num] -= 1
				if d[-num] == 0:
					del d[-num]
			elif -k - num in d and d[-k - num]:
				d[-k - num] -= 1
				if d[-k - num] == 0:
					del d[-k - num]
			elif k - num in d and d[k - num]:
				d[k - num] -= 1
				if d[k - num] == 0:
					del d[k - num]
			else:
				d[num] += 1
		return len(d) == 0


class Solution:

	def canArrange(self, arr: List[int], k: int) -> bool:
		hashtable = dict()
		count = 0
		for x in arr:
			corresp = abs(k - x % k)
			if corresp in hashtable:
				if k - corresp == corresp:
					if hashtable[corresp] == 1:
						hashtable[corresp] = 0
					else:
						hashtable[corresp] = 1
				else:
					hashtable[corresp] -= 1
			elif k - corresp in hashtable:
				if k - corresp != 0:
					hashtable[k - corresp] += 1
				else:
					hashtable[k - corresp] = 0
			else:
				hashtable[k - corresp] = 1
		print(count)
		for x in hashtable:
			if hashtable[x] != 0:
				print(x, hashtable[x])
				return False
		return True


class Solution:

	def canArrange(self, arr: List[int], k: int) -> bool:
		n = len(arr)
		if n % 2:
			return False
		tbl = dict()
		for val in arr:
			r = val % k
			if tbl.get((k - r) % k, 0):
				tbl[(k - r) % k] -= 1
			else:
				tbl[r] = tbl.get(r, 0) + 1
		for (idx, cnt) in tbl.items():
			if cnt != 0:
				return False
		return True


class Solution:

	def canArrange(self, arr: List[int], k: int) -> bool:
		a = arr
		c = collections.Counter()
		for x in a:
			r = x % k
			t = k - r if r else r
			if t in c:
				c[t] -= 1
				if c[t] == 0:
					del c[t]
			else:
				c[r] += 1
		return not c


class Solution:

	def canArrange(self, arr: List[int], k: int) -> bool:
		from collections import Counter
		mods = [a % k for a in arr]
		c = Counter(mods)
		possible = True
		print(c)
		for (val, ct) in c.items():
			complement = (k - val) % k
			if complement == val:
				possible &= ct % 2 == 0
			else:
				possible &= c[complement] == ct
		return possible


class Solution:

	def canArrange(self, arr: List[int], k: int) -> bool:
		d = collections.Counter([i % k for i in arr])
		pair = 0
		for i in list(d.keys()):
			if k - i == i:
				if i in d:
					if d[i] > 1:
						pair += d[i] // 2
						d[i] = 0
					else:
						continue
			if k - i in d:
				t = min(d[i], d[k - i])
				pair += t
				d[i] -= t
				d[k - i] -= t
		if 0 in d:
			pair += d[0] // 2
			d[0] = 0
		print(pair)
		if pair == len(arr) // 2:
			return 1
		return 0


from collections import Counter

class Solution:

	def canArrange(self, arr: List[int], k: int) -> bool:
		mods = [x % k for x in arr]
		cMods = Counter(mods)
		totalP = 0
		for cm in cMods:
			if cm == 0 or cMods[cm] == 0:
				totalP += cMods[cm]
				continue
			if cMods[cm] != cMods[k - cm]:
				return False
		if cMods[0] % 2 == 0:
			return True
		else:
			return False


class Solution:

	def canArrange(self, arr: List[int], k: int) -> bool:
		freq = Counter([x % k for x in arr])
		for num in arr:
			if freq[num % k] == 0:
				continue
			freq[num % k] -= 1
			if freq[(k - num % k) % k] == 0:
				return False
			freq[(k - num % k) % k] -= 1
		return True


class Solution:

	def canArrange(self, arr: List[int], k: int) -> bool:
		if len(arr) % 2 != 0:
			return False
		lookup = [0] * k
		for num in arr:
			lookup[num % k] += 1
		if lookup[0] % 2 != 0:
			return False
		for p in range(1, k):
			if p != k - p:
				if lookup[p] != lookup[k - p]:
					return False
			elif lookup[p] % 2 != 0:
				return False
		return True


from collections import Counter

class Solution:

	def canArrange(self, arr: List[int], k: int) -> bool:
		matches = Counter()
		c = 0
		for e in arr:
			me = -e % k
			if matches[me] > 0:
				matches[me] -= 1
				c += 1
			else:
				matches[e % k] += 1
		return c == len(arr) // 2


class Solution:

	def canArrange(self, arr: List[int], k: int) -> bool:
		if len(arr) == 0:
			return False
		if len(arr) % 2 != 0:
			return False
		Check = dict()
		for i in range(len(arr)):
			if arr[i] % k not in Check:
				Check[arr[i] % k] = 0
			Check[arr[i] % k] += 1
		if 0 in Check and Check[0] % 2 != 0:
			return False
		for i in range(1, k):
			if i in Check:
				if k - i not in Check or Check[i] != Check[k - i]:
					return False
		return True


class Solution:

	def canArrange(self, arr: List[int], k: int) -> bool:
		tmp = collections.Counter()
		for x in arr:
			tmp[x % k] += 1
		for (c, v) in list(tmp.items()):
			if c == 0 and v % 2 != 0:
				return False
			elif c != 0 and v != tmp[k - c]:
				return False
		return True


class Solution:

	def canArrange(self, arr: List[int], k: int) -> bool:
		countMap = {}
		for i in range(len(arr)):
			arr[i] %= k
			countMap[arr[i]] = countMap.get(arr[i], 0) + 1
		print((countMap, arr))
		for char in arr:
			if char == 0:
				continue
			if k - char not in countMap:
				return False
			elif countMap[k - char] == 0:
				return False
			else:
				countMap[k - char] -= 1
		return True if 0 not in countMap or countMap[0] % 2 == 0 else False


class Solution:

	def canArrange(self, arr: List[int], k: int) -> bool:
		arr = sorted([c % k for c in arr])
		count = Counter(arr)
		for i in range(len(arr) // 2):
			if count[arr[i]] > 0:
				count[arr[i]] -= 1
				if count[(k - arr[i]) % k] == 0:
					return False
				else:
					count[(k - arr[i]) % k] -= 1
		return True


class Solution:

	def canArrange(self, arr: List[int], k: int) -> bool:
		arr = [a % k for a in arr]
		arr = Counter(arr)
		if arr.get(0, 0) % 2 != 0:
			return False
		if k % 2 == 0 and arr.get(k / 2, 0) % 2 == 1:
			return False
		i = 1
		k -= 1
		while k > i:
			if arr.get(k, 0) != arr.get(i, 0):
				return False
			i += 1
			k -= 1
		return True


class Solution:

	def canArrange(self, arr: List[int], k: int) -> bool:
		rem = collections.Counter()
		for a in arr:
			rem[a % k] += 1
		for a in arr:
			one = a % k
			if rem[one] == 0:
				continue
			rem[one] -= 1
			two = one if one == 0 else k - one
			if rem[two] == 0:
				return False
			rem[two] -= 1
		return True


class Solution:

	def canArrange(self, arr: List[int], k: int) -> bool:
		count = [0] * k
		for num in arr:
			count[num % k] += 1
		print('count ', count)
		for x in range(k):
			comp = -x % k
			print('Comp : ', comp)
			while count[x] > 0:
				count[x] -= 1
				count[comp] -= 1
				if count[comp] < 0:
					return False
		return True


class Solution:

	def canArrange(self, arr: List[int], k: int) -> bool:
		counts = defaultdict(lambda : 0)
		for n in arr:
			mod = n % k
			if counts[k - mod] == 0:
				counts[mod] += 1
			else:
				counts[k - mod] -= 1
		return counts[0] % 2 == 0 and sum(counts.values()) - counts[0] == 0


class Solution:

	def canArrange(self, arr: List[int], k: int) -> bool:
		n = len(arr)
		mod_count = [0 for i in range(0, k)]
		for i in range(0, n):
			mod_count[arr[i] % k] += 1
		mid = int(k / 2)
		if k % 2 == 1:
			if mod_count[0] % 2 == 1:
				return False
		elif mod_count[0] % 2 == 1 or mod_count[mid] % 2 == 1:
			return False
		num = int((k - 1) / 2)
		for i in range(1, num + 1):
			if mod_count[i] != mod_count[k - i]:
				return False
		return True


class Solution:

	def canArrange(self, arr: List[int], k: int) -> bool:
		n = len(arr)
		if n & 1:
			return False
		bucket = [0] * k
		for a in arr:
			bucket[(k + a % k) % k] += 1
		if bucket[0] % 2:
			return False
		for i in range(1, k):
			if bucket[i] != bucket[k - i]:
				return False
		return True


class Solution:

	def canArrange(self, A: List[int], K: int) -> bool:
		counts = [0] * K
		for num in A:
			counts[num % K] += 1
		for x in range(K):
			y = -x % K
			while counts[x]:
				counts[x] -= 1
				counts[y] -= 1
				if counts[y] < 0:
					return False
		return True


class Solution:

	def canArrange(self, arr: List[int], k: int) -> bool:
		n = len(arr)
		modulo_map = defaultdict(lambda : [])
		pairs = []
		for a in arr:
			r = k - a % k if a % k != 0 else 0
			if r in list(modulo_map.keys()) and len(modulo_map[r]) > 0:
				pairs.append((a, modulo_map[r].pop(-1)))
				if len(modulo_map[r]) == 0:
					del modulo_map[r]
			else:
				modulo_map[a % k].append(a)
		if len(pairs) == n // 2:
			return True
		else:
			return False


class Solution:

	def canArrange(self, arr: List[int], k: int) -> bool:
		h = collections.Counter((i % k for i in arr))
		if 0 in h:
			if h[0] % 2 != 0:
				return False
		for x in h:
			if x > 0 and h[x] != h[k - x]:
				return False
		return True


class Solution:

	def canArrange(self, arr: List[int], k: int) -> bool:
		n = len(arr)
		if n % 2:
			return 0
		d = defaultdict(int)
		for a in arr:
			d[a % k] += 1
		if k % 2 == 0 and k // 2 in d:
			if d[k // 2] % 2:
				return 0
			del d[k // 2]
		sd = sorted(d.items(), key=lambda x: x[0])
		if sd[0][0] == 0:
			if sd[0][1] % 2:
				return 0
			sd.pop(0)
		if n % 2 and len(sd) % 2:
			return 0
		while sd:
			a1 = sd.pop(0)
			s2 = sd.pop(-1)
			if a1[0] + s2[0] != k or a1[1] != s2[1]:
				return 0
		return 1


class Solution:

	def canArrange(self, arr: List[int], k: int) -> bool:
		seen = {}
		for num in arr:
			remainder = num % k
			if remainder in seen:
				seen[remainder] -= 1
				if seen[remainder] == 0:
					del seen[remainder]
			elif remainder == 0:
				seen[remainder] = 1
			else:
				seen[k - remainder] = seen.get(k - remainder, 0) + 1
		return len(seen) == 0


class Solution:

	def canArrange(self, arr: List[int], k: int) -> bool:
		n = len(arr)
		for i in range(n):
			arr[i] = arr[i] % k
		lookup = defaultdict(int)
		for i in range(n):
			if not arr[i]:
				continue
			if k - arr[i] in lookup:
				lookup[k - arr[i]] -= 1
				if not lookup[k - arr[i]]:
					lookup.pop(k - arr[i])
			else:
				lookup[arr[i]] += 1
		if not lookup:
			return True
		return False


class Solution:

	def canArrange(self, arr: List[int], k: int) -> bool:
		dic = collections.defaultdict(int)
		for i in range(len(arr)):
			if arr[i] % k != 0:
				dic[arr[i] % k] += 1
		for ki in list(dic.keys()):
			if ki != 0:
				if dic[ki] != dic[k - ki] or (2 * ki == k and dic[ki] % 2 == 1):
					return False
		return True


from collections import Counter

class Solution:

	def canArrange(self, arr: List[int], k: int) -> bool:
		count = Counter((x % k for x in arr))
		for x in count:
			y = -x % k
			if x == 0 and count[x] & 1:
				return False
			elif count[x] != count[y]:
				return False
		return True


import collections as clc

class Solution:

	def canArrange(self, arr: List[int], k: int) -> bool:
		if len(arr) % 2 == 1:
			return False
		counts = clc.Counter([v % k for v in arr])
		if k % 2 == 0:
			if counts[k // 2] % 2 != 0:
				return False
		return all((counts[i] == counts[k - i] for i in range(1, k // 2 + 1)))


class Solution:

	def canArrange(self, arr: List[int], k: int) -> bool:
		count = collections.Counter()
		for i in arr:
			count[i % k] += 1
		for i in range(1, k // 2 + 1):
			if count[i] != count[k - i]:
				return False
			if count[0] % 2 != 0:
				return False
		return True