Given an array of integers and a number k, write a function that returns true if given array can be divided into pairs such that sum of every pair is divisible by k.
 
Example 1 :
Input : arr = [9, 5, 7, 3], k = 6
Output: True
Explanation: {(9, 3), (5, 7)} is a 
possible solution. 9 + 3 = 12 is divisible
by 6 and 7 + 5 = 12 is also divisible by 6.
Example 2:
Input : arr = [2, 4, 1, 3], k = 4
Output: False
Explanation: There is no possible solution.
 
Your Task:
You don't need to read or print anything. Your task is to complete the function canPair() which takes array and k as input parameter and returns true if array can be divided into pairs such that sum of every pair is divisible by k otherwise returns false.
 
Expected Time Complexity: O(n)
Expected Space Complexity : O(n)
 
Constraints:
1 <= length of array <= 10^5
1 <= elements of array <= 10^5
1 <= k <= 10^5

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: String algorithms

Data structures

Starter code: #User function Template for python3



class Solution:

	def canPair(self, nuns, k):

		# Code here

Solutions:
class Solution:

	def canPair(self, nums, k):
		remainder_count = {}
		for num in nums:
			remainder = num % k
			if remainder in remainder_count:
				remainder_count[remainder] += 1
			else:
				remainder_count[remainder] = 1
		for num in nums:
			remainder = num % k
			complement = (k - remainder) % k
			if remainder == complement:
				if remainder_count[remainder] % 2 != 0:
					return False
			elif remainder_count.get(remainder, 0) != remainder_count.get(complement, 0):
				return False
		return True


class Solution:

	def canPair(self, nums, k):
		l = [0] * k
		for i in nums:
			y = i % k
			if l[(k - y) % k] != 0:
				l[(k - y) % k] -= 1
			else:
				l[y] += 1
		for i in l:
			if i != 0:
				return False
		return True


from collections import defaultdict

class Solution:

	def canPair(self, arr, k):
		if n & 1:
			return 0
		freq = defaultdict(lambda : 0)
		for i in range(0, n):
			freq[(arr[i] % k + k) % k] += 1
		for i in range(0, n):
			rem = (arr[i] % k + k) % k
			if 2 * rem == k:
				if freq[rem] % 2 != 0:
					return 0
			elif rem == 0:
				if freq[rem] & 1:
					return 0
			elif freq[rem] != freq[k - rem]:
				return 0
		return 1


from collections import defaultdict

class Solution:

	def canPair(self, nuns, k):
		hashmap = defaultdict(lambda : 0)
		for i in range(len(nuns)):
			if hashmap[(k - nuns[i] % k) % k] > 0:
				hashmap[(k - nuns[i] % k) % k] -= 1
			else:
				hashmap[nuns[i] % k] += 1
		for (x, y) in list(hashmap.items()):
			if y != 0:
				return False
		return True


class Solution:

	def canPair(self, nuns, k):
		a = max(nuns)
		b = max(k, a + 1)
		arr_f = [0] * b
		arr_fi = [0] * b
		c1 = 0
		c2 = 0
		if k == 1:
			return True
		if k == 2:
			for i in nuns:
				if i % 2 != 0:
					c1 = c1 + 1
			if c1 % 2 == 0:
				return True
		if len(nums) == 2:
			if sum(nums) % k == 0:
				return True
		for i in nuns:
			arr_f[i] = arr_f[i] + 1
		ce = 0
		h = set()
		for i in nuns:
			if arr_f[k - i % k] > 0:
				if k - i % k != i:
					if i > k - i % k:
						h.add((i, k - i % k))
					elif k - i % k > i:
						h.add((k - i % k, i))
					else:
						h.add((i, i))
				elif k - i % k == i and arr_f[i] > 1:
					h.add((i, k - i % k))
			arr_f[i] = arr_f[i] - 1
			arr_f[k - i % k] = arr_f[k - i % k]
			if i % k == 0:
				ce = ce + 1
		if len(h) == len(nums) // 2:
			return True
		if ce == len(nuns):
			return True


class Solution:

	def canPair(self, nuns, k):
		freq_arr = [0] * k
		for i in nuns:
			y = i % k
			if freq_arr[(k - y) % k] != 0:
				freq_arr[(k - y) % k] -= 1
			else:
				freq_arr[y] += 1
		for i in freq_arr:
			if i > 0:
				return False
		return True


class Solution:

	def canPair(self, nuns, k):
		d = {}
		nums = []
		if len(nums) % 2 == 1:
			return False
		for i in range(len(nuns)):
			l = nuns[i] % k
			nuns[i] = l
			if l not in d:
				d[l] = 1
			else:
				d[l] = d[l] + 1
		for i in range(len(nuns)):
			if nuns[i] in d:
				if nuns[i] == 0 and d[nuns[i]] % 2 == 0:
					del d[nuns[i]]
				elif (k - nuns[i]) % k in d:
					d[(k - nuns[i]) % k] -= 1
					d[nuns[i]] -= 1
					if d[nuns[i]] == 0:
						del d[nuns[i]]
					if (k - nuns[i]) % k in d and d[(k - nuns[i]) % k] == 0:
						del d[(k - nuns[i]) % k]
				else:
					return False
		if len(d) > 0:
			return False
		return True


class Solution:

	def canPair(self, nuns, k):
		res = [0] * k
		for i in nuns:
			a = i % k
			if res[(k - a) % k] != 0:
				res[(k - a) % k] -= 1
			else:
				res[a] += 1
		for i in res:
			if i != 0:
				return False
		return True


from collections import defaultdict

class Solution:

	def canPair(self, arr, k):
		data = defaultdict(lambda : 0)
		for e1 in arr:
			rem = e1 % k
			data[rem] += 1
		for e2 in arr:
			rem = e2 % k
			if 2 * rem == k:
				if data[rem] % 2 != 0:
					return False
			elif rem == 0:
				if data[rem] % 2 != 0:
					return False
			elif data[rem] != data[k - rem]:
				return False
		return True


class Solution:

	def canPair(self, nums, k):
		d = {}
		for i in range(k):
			d[i] = 0
		for ele in nums:
			d[ele % k] += 1
		for i in range(1, k // 2 + 1):
			if d[i] != d[k - i]:
				return False
		if k % 2 == 0:
			if d[k // 2] % 2 == 1:
				return False
		if d[0] % 2 == 1:
			return False
		return True


class Solution:

	def canPair(self, nuns, k):
		if len(nuns) % 2 != 0:
			return False
		freq = [0] * k
		for i in nuns:
			r = i % k
			freq[r] += 1
		if freq[0] % 2 != 0:
			return False
		for r in range(1, k // 2 + 1):
			if freq[r] != freq[k - r]:
				return False
		return True


from collections import defaultdict as dd

class Solution:

	def canPair(self, nuns, k):
		e = [0] * k
		for i in nuns:
			e[i % k] += 1
		if e[0] % 2 == 1:
			return False
		for i in range(1, k // 2 + 1):
			if e[i] != e[k - i]:
				return False
		return True


class Solution:

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


from collections import defaultdict

class Solution:

	def canPair(self, arr, k):
		if len(arr) % 2 != 0:
			return 0
		d = defaultdict(lambda : 0)
		for i in arr:
			d[i % k] = d.get(i % k, 0) + 1
		for i in arr:
			x = i % k
			if 2 * x == k:
				if d[x] % 2 != 0:
					return 0
			elif x == 0:
				if d[x] % 2 != 0:
					return 0
			elif d[x] != d[k - x]:
				return 0
		return 1


class Solution:

	def canPair(self, nums, k):
		freq = {}
		for i in range(len(nums)):
			rem = nums[i] % k
			if rem in freq:
				freq[rem] += 1
			else:
				freq[rem] = 1
		for i in range(len(nums)):
			rem = nums[i] % k
			if rem == 0:
				if freq[rem] % 2 != 0:
					return False
			elif k - rem in freq:
				if freq[rem] != freq[k - rem]:
					return False
			else:
				return False
		return True


class Solution:

	def canPair(self, nuns, k):
		freq = {}
		for val in range(k):
			freq[val] = 0
		for val in nuns:
			if val % k in freq:
				freq[val % k] += 1
			else:
				freq[val % k] = 1
		if freq[0] % 2 == 1:
			return False
		for i in range(1, k):
			if freq[i] != freq[k - i]:
				return False
		return True


class Solution:

	def canPair(self, arr, k):
		freq = {}
		for i in range(k):
			freq[i] = 0
		for i in arr:
			temp = i % k
			freq[temp] += 1
		for i in freq:
			if i == 0 or (k % 2 == 0 and i == k // 2):
				if freq[i] % 2 != 0:
					break
			elif freq[i] != freq[k - i]:
				break
		else:
			return True
		return False


from collections import Counter

class Solution:

	def canPair(self, nums, k):
		for i in range(len(nums)):
			nums[i] %= k
		C = Counter(nums)
		for i in nums:
			if i == 0:
				if C[i] > 1:
					C[i] -= 2
					continue
			if C[i] > 0:
				C[i] -= 1
				if C[k - i] > 0:
					C[k - i] -= 1
				else:
					return False
		return sum(C.values()) == 0


from collections import Counter

class Solution:

	def canPair(self, nuns, k):
		arr = []
		pair = []
		for i in range(0, len(nuns)):
			c = nuns[i] % k
			arr.append(c)
		dic = Counter(arr)
		for i in dic:
			if i == k / 2:
				if dic[i] % 2 != 0:
					return 0
			elif i == 0:
				if dic[i] % 2 != 0:
					return 0
			elif dic[i] != dic[k - i]:
				return 0
		return 1


from collections import defaultdict

class Solution:

	def canPair(self, nums, k):
		n = len(nums)
		c = defaultdict(int)
		for i in range(n):
			c[nums[i] % k] += 1
		for i in range(n):
			rem = nums[i] % k
			if rem == 0:
				if c[0] % 2 == 1:
					return False
			elif c[rem] != c[k - rem]:
				return False
		return True


class Solution:

	def canPair(self, nuns, k):
		map = {}
		for i in nuns:
			rem = i % k
			if rem in map:
				map[rem] += 1
			else:
				map[rem] = 1
		for i in nuns:
			rem = i % k
			if rem == 0:
				if map[rem] % 2 != 0:
					return False
			elif rem == k - rem:
				if map[rem] % 2 != 0:
					return False
			elif k - rem not in map:
				return False
			elif map[rem] != map[k - rem]:
				return False
		return True
		return True


from collections import defaultdict

class Solution:

	def canPair(self, nums, k):
		hm = defaultdict(int)
		res = 0
		for i in nums:
			t = i % k
			if t == 0:
				res += 1
			elif k - t in hm and hm[k - t] > 0:
				res += 2
				hm[k - t] -= 1
			else:
				hm[t] += 1
		return res == len(nums)


class Solution:

	def canPair(self, arr, k):
		freq = {}
		for num in nums:
			rem = num % k
			freq[rem] = freq.get(rem, 0) + 1
		for rem in freq.keys():
			if rem == 0:
				if freq[rem] % 2 != 0:
					return False
			elif k - rem not in freq or freq[k - rem] < freq[rem]:
				return False
		return True


class Solution:

	def canPair(self, a, k):
		if len(a) % 2 != 0:
			return False
		d = dict()
		for i in a:
			if d.get(i % k) != None:
				d[i % k] = d[i % k] + 1
			if d.get(i % k) == None:
				d[i % k] = 1
		for i in d.keys():
			if i == 0:
				if d[i] % 2 != 0:
					return False
				continue
			if d.get(k - i) == None:
				return False
			if k - i == i:
				if d[i] % 2 != 0:
					return False
				continue
			if d[k - i] != d[i]:
				return False
		return True


from collections import defaultdict

class Solution:

	def canPair(self, nuns, k):
		m = defaultdict(int)
		for i in nuns:
			i %= k
			if m[i] > 0:
				m[i] -= 1
			else:
				m[(k - i) % k] += 1
		if sum(m.values()) == 0:
			return True
		return False


from collections import defaultdict

class Solution:

	def canPair(self, nuns, k):
		m = defaultdict(int)
		for e in nuns:
			e %= k
			if m[e] > 0:
				m[e] -= 1
			else:
				m[(k - e) % k] += 1
		return sum(m.values()) == 0


class Solution:

	def canPair(self, nums, k):
		pair_dict = {}
		for i in nums:
			if i % k in pair_dict.keys():
				pair_dict[i % k] += 1
			else:
				pair_dict[i % k] = 1
		for i in pair_dict:
			if i == 0:
				if pair_dict[i] % 2 != 0:
					return False
			elif i == k / 2:
				if pair_dict[i] % 2 != 0:
					return False
			elif i in pair_dict.keys() and k - i in pair_dict.keys() and (pair_dict[i] == pair_dict[k - i]):
				continue
			else:
				return False
		return True


class Solution:

	def canPair(self, nums, k):
		if len(nums) % 2 == 1:
			return False
		temp = [0] * k
		for i in nums:
			n = i % k
			temp[i % k] += 1
		return temp[1:] == temp[1:][::-1] and temp[0] % 2 == 0


from collections import defaultdict

class Solution:

	def canPair(self, nuns, k):
		n = len(nuns)
		freq = defaultdict(int)
		for i in range(n):
			rem = nuns[i] % k
			freq[rem] += 1
		if freq[0] % 2 != 0:
			return 0
		for i in range(1, k):
			if freq[i] != freq[k - i]:
				return 0
		return 1


class Solution:

	def canPair(self, nuns, k):
		if len(nums) % 2 != 0:
			return False
		l = []
		for i in range(len(nums)):
			if nums[i] % k != 0:
				l.append(nums[i] % k)
		l.sort()
		i = 0
		j = len(l) - 1
		if len(l) % 2 != 0:
			return False
		while i < j:
			if (l[i] + l[j]) % k == 0:
				i += 1
				j -= 1
			else:
				return False
		return True


class Solution:

	def canPair(self, arr, k):
		n = len(arr)
		if n % 2 != 0:
			return False
		freq = {}
		for a in arr:
			r = a % k
			freq[r] = freq.get(r, 0) + 1
		for a in arr:
			r = a % k
			if r == 0:
				if freq[r] % 2 != 0:
					return False
			elif freq.get(k - r, 0) < freq[r]:
				return False
		return True


class Solution:

	def canPair(self, nums, k):
		arr = [0 for i in range(k)]
		for i in nums:
			arr[i % k] += 1
		i = 0
		for i in range(k):
			if i == 0:
				if arr[i] % 2 != 0:
					return False
			elif arr[i] > 0:
				if arr[i] != arr[k - i]:
					return False
		return True


class Solution:

	def canPair(self, nuns, k):
		d = {}
		for j in range(0, len(nuns)):
			nuns[j] = nuns[j] % k
			if nuns[j] in d:
				d[nuns[j]] += 1
			else:
				d[nuns[j]] = 1
		c = 0
		for j in range(0, len(nuns)):
			if nuns[j] != 0:
				if k - nuns[j] in d and d[k - nuns[j]] >= 1:
					d[k - nuns[j]] -= 1
					c += 1
				else:
					return False
			elif d[0] % 2 != 0:
				return False
		return True


from collections import Counter

class Solution:

	def canPair(self, nums, k):
		c = Counter(map(lambda x: x % k, nums))
		for num in c:
			if not num and c[num] % 2 or (num and c[num] != c[k - num]):
				return False
		return True


import collections

class Solution:

	def canPair(self, nums, k):
		for (pos, item) in enumerate(nums):
			nums[pos] = item % k
		mp = collections.Counter(nums)
		for (pos, item) in enumerate(nums):
			if item == 0:
				if mp[item] % 2 != 0:
					return False
			else:
				if k - item not in mp:
					return False
				mp[k - item] -= 1
				if mp[k - item] == 0:
					mp.pop(k - item)
		return True


class Solution:

	def canPair(self, l1, n):
		l = [0] * n
		for i in l1:
			l[i % n] += 1
		if l[0] % 2 != 0:
			return False
		else:
			for i in range(1, n):
				if l[i] != l[n - i]:
					return False
		return True


class Solution:

	def canPair(self, nuns, k):
		dict1 = dict()
		length = len(nuns)
		count = 0
		for i in range(length):
			if nuns[i] % k not in dict1:
				dict1[nuns[i] % k] = 1
			else:
				dict1[nuns[i] % k] += 1
		for i in dict1:
			if k - i in dict1 and i < k - i:
				count += min(dict1[k - i], dict1[i])
				dict1[k - i] -= count
				dict1[i] -= count
			elif k - i in dict1 and i == k - i:
				count += dict1[i] // 2
				dict1[i] -= count
			elif i == 0:
				count += dict1[i] // 2
				dict1[i] -= count
		if count == length // 2:
			return True
		return False


class Solution:

	def canPair(self, nuns, k):
		nums = [0] * k
		for n in nuns:
			nums[n % k] += 1
		for i in range(k // 2 + 1):
			if i == 0 and nums[i] % 2:
				return False
			elif nums[i] != nums[-i]:
				return False
		if not k % 2 and nums[k // 2] % 2:
			return False
		return True


class Solution:

	def canPair(self, nums, k):
		hp = [0 for i in range(k)]
		for i in range(len(nums)):
			hp[nums[i] % k] += 1
		if hp[0] % 2 != 0:
			return False
		for i in range(len(nums)):
			if nums[i] % k == 0:
				continue
			if hp[k - nums[i] % k] > 0:
				hp[k - nums[i] % k] -= 1
			else:
				return False
		return True


from collections import defaultdict

class Solution:

	def canPair(self, nuns, k):
		if len(nuns) % 2 != 0:
			return False
		freq = defaultdict(lambda : 0)
		for i in range(len(nuns)):
			freq[(nuns[i] % k + k) % k] += 1
		for i in range(len(nuns)):
			rem = (nuns[i] % k + k) % k
			if rem * 2 == k:
				if freq[rem] % 2 != 0:
					return False
			elif rem == 0:
				if freq[rem] % 2 != 0:
					return False
			elif freq[rem] != freq[k - rem]:
				return False
		return True


class Solution:

	def canPair(self, a, k):
		if len(a) % 2 != 0:
			return 0
		arr = [0] * k
		for i in a:
			arr[i % k] = arr[i % k] + 1
		p = 1
		q = len(arr) - 1
		if arr[0] % 2 != 0:
			return 0
		while p < q:
			if arr[p] != arr[q]:
				return 0
			p += 1
			q -= 1
		return 1


class Solution:

	def canPair(self, nuns, k):
		l = [0] * k
		for i in nuns:
			m = i % k
			if l[(k - m) % k] != 0:
				l[(k - m) % k] -= 1
			else:
				l[m] += 1
		for i in l:
			if i != 0:
				return False
		return True


class Solution:

	def canPair(self, nuns, k):
		di = {x: 0 for x in range(k)}
		for x in nums:
			di[x % k] += 1
		if not di[0] & 1:
			for x in range(1, k):
				if di[x] != di[k - x]:
					return False
			return True
		return False


class Solution:

	def canPair(self, nuns, k):
		mp = {}
		for x in nuns:
			rem = x % k
			if rem in mp:
				mp[rem] += 1
			else:
				mp[rem] = 1
		for x in nuns:
			rem = x % k
			if rem == 0:
				if mp[rem] % 2 == 1:
					return False
			elif rem * 2 == k:
				if mp[rem] % 2 == 1:
					return False
			else:
				if k - rem not in mp:
					val = 0
				else:
					val = mp[k - rem]
				if mp[rem] != val:
					return False
		return True


class Solution:

	def canPair(self, nuns, k):
		D = {}
		for i in nums:
			if i % k in D.keys():
				D[i % k] += 1
			else:
				D[i % k] = 1
		for i in D.keys():
			if abs(k - i) == k and D[abs(i)] % 2 == 0:
				continue
			if abs(k - i) == k and D[abs(i)] % 2 != 0:
				return False
			if abs(k - i) not in D.keys() or D[i] != D[abs(k - i)]:
				return False
		return True


from collections import Counter

class Solution:

	def canPair(self, nums, k):
		mods = Counter((n % k for n in nums))
		if 0 in mods:
			if mods[0] % 2 == 1:
				return False
			else:
				del mods[0]
		for key in mods:
			if mods[key] != mods.get(k - key):
				return False
		return True


from collections import Counter

class Solution:

	def canPair(self, nums, k):
		u = []
		a = 0
		b = 0
		c = 0
		for i in range(len(nums)):
			u.append(nums[i] % k)
		e = Counter(u)
		if e[0] % 2 != 0:
			return False
		else:
			for r in range(1, k // 2 + 1):
				if e[r] != e[k - r]:
					return False
			return True


class Solution:

	def canPair(self, nums, k):
		counter = {}
		hash = {}
		count = 0
		for i in nums:
			hash[i] = i % k
			counter[i % k] = counter.get(i % k, 0) + 1
			count += 1
		if count % 2 != 0:
			return False
		for i in nums:
			rem = i % k
			if rem == 0:
				if counter[0] % 2 != 0:
					return False
				continue
			if counter.get(k - rem, -1) != -1:
				if counter[k - rem] != counter[rem]:
					return False
			else:
				return False
		return True


from collections import defaultdict

class Solution:

	def canPair(self, arr, k):
		if len(arr) % 2 != 0:
			return False
		freq = defaultdict(lambda : 0)
		for i in range(len(arr)):
			freq[(arr[i] % k + k) % k] += 1
		for i in range(n):
			r = (arr[i] % k + k) % k
			if 2 * r == k:
				if freq[r] % 2 != 0:
					return False
			elif r == 0:
				if freq[r] % 2 != 0:
					return False
			elif freq[r] != freq[k - r]:
				return False
		return True


class Solution:

	def canPair(self, nuns, k):
		if sum(nuns) % k == 0:
			nuns = [i % k for i in nuns]
			count_0 = 0
			for i in nuns:
				if i == 0:
					count_0 = count_0 + 1
			if count_0 % 2 != 0:
				return False
			else:
				dic = {}
				for i in range(k):
					dic[i] = 0
				for i in nuns:
					if i in dic:
						dic[i] = dic[i] + 1
				for i in range(1, int(k / 2)):
					if dic[i] != dic[k - i]:
						return False
				return True
		return False


from collections import defaultdict

class Solution:

	def canPair(self, nuns, k):
		n = len(nuns)
		nums = nuns
		if n % 2 == 1:
			return False
		freq_dict = defaultdict(int)
		for digit in nums:
			remainder = (digit % k + k) % k
			freq_dict[remainder] = 1 + freq_dict[remainder]
		for i in range(n):
			digit = nums[i]
			remainder = (digit % k + k) % k
			if 2 * remainder == k:
				if freq_dict[remainder] % 2 != 0:
					return False
			elif remainder == 0:
				if freq_dict[remainder] & freq_dict[remainder] == 1:
					return False
			elif freq_dict[remainder] != freq_dict[k - remainder]:
				return False
		return True


class Solution:

	def canPair(self, nuns, k):
		(dic, j) = ({}, 1)
		if len(nums) % 2 != 0:
			return False
		for num in nums:
			temp = num % k
			if temp in dic:
				dic[temp] += 1
			else:
				dic[temp] = 1
		if 0 in dic and dic[0] % 2 != 0:
			return False
		for i in range(k - 1, k // 2, -1):
			if i in dic and j in dic:
				if dic[i] != dic[j]:
					return False
			elif i in dic and j not in dic:
				return False
			elif i not in dic and j in dic:
				return False
			j += 1
		if k % 2 == 0 and k // 2 in dic and (dic[k // 2] % 2 != 0):
			return False
		return True


class Solution:

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


class Solution:

	def canPair(self, nuns, k):
		s = {}
		for i in nuns:
			if i % k not in s:
				s[i % k] = 0
			s[i % k] += 1
		for i in nuns:
			if s[i % k] == 0:
				continue
			if k - i % k in s and s[k - i % k] > 0:
				s[i % k] -= 1
				s[k - i % k] -= 1
			elif i % k == 0 and s[0] > 0:
				s[0] -= 1
				if k in s:
					s[k] -= 1
				else:
					s[0] -= 1
			else:
				return False
		return True


class Solution:

	def canPair(self, nuns, k):
		if sum(nuns) % k != 0 or len(nuns) % 2 != 0:
			return False
		else:
			for i in range(len(nuns)):
				nuns[i] = nuns[i] % k
			if nuns.count(0) % 2 != 0:
				return False
			for i in range(1, k // 2 + 1):
				if nuns.count(i) != nuns.count(k - i):
					return False
		return True


class Solution:

	def canPair(self, nuns, k):
		v = [0] * k
		for i in nuns:
			rem = i % k
			v[rem] += 1
		if v[0] % 2 == 1:
			return 0
		for i in range(1, k):
			if v[i] != v[k - i]:
				return 0
		return 1


class Solution:

	def canPair(self, nuns, k):
		if len(nums) % 2 != 0:
			return False
		mod_counts = [0] * k
		for x in nums:
			mod_counts[x % k] += 1
		if mod_counts[0] % 2 != 0:
			return False
		for i in range(1, k // 2 + 1):
			if mod_counts[i] != mod_counts[k - i]:
				return False
		return True


class Solution:

	def canPair(self, arr, k):
		for i in range(len(arr)):
			arr[i] = arr[i] % k
		d = {}
		for i in range(0, len(arr)):
			if arr[i] in d:
				d[arr[i]] += 1
			else:
				d[arr[i]] = 1
		for i in d:
			if k - i == i or i == 0:
				if d[i] % 2 != 0:
					return False
				continue
			if k - i not in d or d[k - i] != d[i]:
				return False
		return True


class Solution:

	def canPair(self, nums, k):
		MAX_SIZE = k
		arr = [0 for i in range(MAX_SIZE)]
		for i in range(len(nums)):
			h = nums[i] % k
			arr[h] += 1
		if arr[0] % 2 != 0:
			return False
		for i in range(1, MAX_SIZE // 2 + 1):
			if arr[i] != arr[MAX_SIZE - i]:
				return False
		return True
		if len(nums) % 2 != 0:
			return False
		a = []
		i = 0
		while i < len(nums) / 2:
			n = 0
			j = i + 1
			while j < len(nums):
				if (nums[i] + nums[j]) % k == 0:
					n += 1
					a.append([nums[i], nums[j]])
					nums.remove(nums[i])
					nums.remove(nums[j - 1])
					break
				j += 1
			if n == 0:
				return False
		return a


class Solution:

	def canPair(self, nuns, k):
		M = [0 for _ in range(k)]
		for v in nuns:
			rem = v % k
			M[rem] += 1
		i = 0
		while i < k:
			j = (k - i) % k
			if not i <= j:
				break
			if i == j:
				if M[i] % 2 != 0:
					return False
			elif M[i] != M[j]:
				return False
			i += 1
		return True


from collections import defaultdict

class Solution:

	def canPair(self, nums, k):
		n = len(nums)
		if n % 2 == 1:
			return False
		has = defaultdict(lambda : False)
		count = 0
		for num in nums:
			rem = num % k
			temp = k - rem if k - rem < k else 0
			if has[temp]:
				has[temp] = False
				count += 1
			else:
				has[rem] = True
		return count == n // 2


class Solution:

	def canPair(self, nuns, k):
		cM = [0] * k
		for i in nuns:
			p = i % k
			if cM[(k - p) % k] != 0:
				cM[(k - p) % k] -= 1
			else:
				cM[p] += 1
		for i in cM:
			if i != 0:
				return False
		return True


class Solution:

	def canPair(self, nuns, k):
		if len(nuns) % 2 == 1:
			return False
		freqMap = {}
		for i in nuns:
			if i % k not in freqMap:
				freqMap[i % k] = 1
			else:
				freqMap[i % k] += 1
		for i in nuns:
			if i % k in freqMap and (k - i % k) % k in freqMap and (freqMap[i % k] != 0) and (freqMap[(k - i % k) % k] != 0):
				freqMap[(k - i % k) % k] -= 1
				freqMap[i % k] -= 1
		for i in freqMap.values():
			if i != 0:
				return False
		return True