Given an array of integers A with even length, return true if and only if it is possible to reorder it such that A[2 * i + 1] = 2 * A[2 * i] for every 0 <= i < len(A) / 2.








 
Example 1:
Input: A = [3,1,3,6]
Output: false

Example 2:
Input: A = [2,1,2,6]
Output: false

Example 3:
Input: A = [4,-2,2,-4]
Output: true
Explanation: We can take two groups, [-2,-4] and [2,4] to form [-2,-4,2,4] or [2,4,-2,-4].

Example 4:
Input: A = [1,2,4,16,8,4]
Output: false

 
Constraints:

0 <= A.length <= 3 * 104
A.length is even.
-105 <= A[i] <= 105

Difficulty: MEDIUM
Tags: Sorting

Data structures

Greedy algorithms
Skill types: Sorting

Data structures

Greedy algorithms

Starter code:
class Solution:
    def canReorderDoubled(self, A: List[int]) -> bool:
        

Solutions:
class Solution:

	def canReorderDoubled(self, A: List[int]) -> bool:
		cache = Counter(A)
		c_list = sorted(list(cache), key=abs)
		for x in c_list:
			if cache[x] > cache[2 * x]:
				return False
			cache[2 * x] -= cache[x]
		return True


from collections import Counter

class Solution:

	def canReorderDoubled(self, A: List[int]) -> bool:
		if len(A) % 2 == 1:
			return False
		if not A:
			return True
		nums = sorted(set(A))
		nums = [x for x in nums if x < 0][::-1] + [x for x in nums if x >= 0]
		c = Counter(A)
		done = set()
		for num in nums:
			if num in done:
				continue
			if 2 * num not in c:
				return False
			if c[2 * num] < c[num]:
				return False
			c[2 * num] -= c[num]
			if c[2 * num] == 0:
				done.add(2 * num)
			c[num] = 0
			done.add(num)
		return True


import collections

class Solution:

	def canReorderDoubled(self, A: List[int]) -> bool:
		if not A:
			return True
		pos = collections.defaultdict(int)
		neg = collections.defaultdict(int)
		zero = 0
		for v in A:
			if v > 0:
				pos[v] += 1
			if v < 0:
				neg[-v] += 1
			if v == 0:
				zero += 1
		b = self.check(pos)
		if not b:
			return False
		b = self.check(neg)
		if not b:
			return False
		return zero % 2 == 0

	def check(self, d):
		while d:
			v = min(d)
			if not 2 * v in d:
				return False
			if d[v] > d[2 * v]:
				return False
			elif d[v] == d[2 * v]:
				del d[v]
				del d[2 * v]
			else:
				d[2 * v] -= d[v]
				del d[v]
		return True


class Solution:

	def canReorderDoubled(self, A: List[int]) -> bool:
		i = 0
		j = 0
		A.sort()
		while i < len(A) and A[i] <= 0:
			if A[i] % 2 != 0:
				return False
			while j < len(A) and A[j] < 0 and (2 * A[j] < A[i]):
				j += 1
			if j >= len(A) or 2 * A[j] > A[i]:
				return False
			A[j] = None
			j += 1
			i += 1
			while i < len(A) and A[i] is None:
				i += 1
		while i < len(A):
			while j < len(A) and A[j] < 2 * A[i]:
				j += 1
			if j >= len(A) or A[j] > 2 * A[i]:
				return False
			A[j] = None
			j += 1
			i += 1
			while i < len(A) and A[i] is None:
				i += 1
		return True


class Solution:

	def canReorderDoubled(self, A: List[int]) -> bool:
		count = {}
		zero_count = 0
		for num in A:
			if num == 0:
				zero_count += 1
			elif num in count:
				count[num] += 1
			else:
				count[num] = 1
		if zero_count % 2 != 0:
			return False
		A.sort()
		for num in A:
			double = num * 2
			if num in count and double in count:
				count[double] -= 1
				count[num] -= 1
				if count[double] == 0:
					count.pop(double)
				if count[num] == 0:
					count.pop(num)
		return count == {}


class Solution:

	def canReorderDoubled(self, A: List[int]) -> bool:
		if len(A) % 2 == 1:
			return False
		count = collections.defaultdict(int)
		for num in A:
			count[num] += 1
		A.sort()
		for num in A:
			if count[num] > 0:
				double = num * 2
				if double in count and count[double] > 0:
					count[num] -= 1
					count[double] -= 1
		for num in count:
			if count[num] != 0:
				return False
		return True


class Solution:

	def canReorderDoubled(self, A: List[int]) -> bool:
		count = collections.Counter(A)
		for x in sorted(A, key=abs):
			if count[x] == 0:
				continue
			if count[2 * x] == 0:
				return False
			count[x] -= 1
			count[2 * x] -= 1
		return True


class Solution:

	def canReorderDoubled(self, A: List[int]) -> bool:
		cache = dict()
		for a in A:
			cache[a] = cache.get(a, 0) + 1
		while len(cache) > 0:
			temp = [abs(k) for k in cache.keys()]
			curr = min(temp)
			if curr == 0:
				if cache[0] % 2 > 0:
					return False
				else:
					cache.pop(0)
			else:
				if curr in cache:
					if cache[curr] == 0:
						cache.pop(curr)
					elif 2 * curr not in cache or cache[2 * curr] < cache[curr]:
						return False
					else:
						cache[2 * curr] -= cache[curr]
						cache.pop(curr)
				if -curr in cache:
					if cache[-curr] == 0:
						cache.pop(-curr)
					elif -2 * curr not in cache or cache[-2 * curr] < cache[-curr]:
						return False
					else:
						cache[-2 * curr] -= cache[-curr]
						cache.pop(-curr)
		return True


class Solution:

	def canReorderDoubled(self, A: List[int]) -> bool:
		counter = collections.Counter(A)
		for v in sorted(counter, key=abs):
			if counter[2 * v] < counter[v]:
				return False
			counter[2 * v] -= counter[v]
		return True


class Solution:

	def canReorderDoubled(self, A: List[int]) -> bool:
		counts = defaultdict(int)
		for x in sorted(A):
			counts[x] += 1
			if x < 0 and x * 2 in counts:
				while counts[x] > 0 and counts[x * 2] > 0:
					counts[x] -= 1
					counts[x * 2] -= 1
			if x >= 0 and x / 2 in counts:
				while counts[x] > 0 and counts[x / 2] > 0:
					counts[x] -= 1
					counts[x / 2] -= 1
		return sum((c for (v, c) in counts.items())) == 0


class Solution:

	def canReorderDoubled(self, A: List[int]) -> bool:
		result = True
		numLen = len(A)
		C = Counter(A)
		val = list(C.keys())
		val.sort()
		for i in range(len(val)):
			if val[i] < 0:
				if val[i] % 2 == 0:
					if val[i] / 2 in val and C[val[i] / 2] >= C[val[i]]:
						C[val[i] / 2] = C[val[i] / 2] - C[val[i]]
						C[val[i]] = 0
					else:
						result = False
			elif val[i] * 2 in val and C[val[i] * 2] >= C[val[i]]:
				C[val[i] * 2] = C[val[i] * 2] - C[val[i]]
				C[val[i]] = 0
			else:
				result = False
		nums = list(C.values())
		if nums == [0] * len(nums):
			result = True
		else:
			result = False
		return result


class Solution:

	def canReorderDoubled(self, A: List[int]) -> bool:
		dd = Counter(A)
		A.sort(key=lambda a: abs(a))
		for a in A:
			if a in dd and dd[a]:
				if 2 * a in dd and dd[2 * a]:
					dd[a] -= 1
					dd[2 * a] -= 1
					if dd[a] == 0:
						del dd[a]
					if dd[a * 2] == 0:
						del dd[a * 2]
				else:
					return False
		return True


class Solution:

	def canReorderDoubled(self, A: List[int]) -> bool:
		A.sort(key=lambda x: (x > 0, abs(x)))
		right = 1
		size = len(A)
		for i in range(size):
			if A[i] is None:
				continue
			while right < size and 2 * A[i] != A[right]:
				right += 1
			if right == size:
				return False
			A[right] = None
		return True


class Solution:

	def canReorderDoubled(self, arr):
		arr.sort()
		negl = [x for x in arr if x < 0][::-1]
		posl = [x for x in arr if x >= 0]
		cnt = {}
		for x in arr:
			if x not in cnt:
				cnt[x] = 1
			else:
				cnt[x] = cnt[x] + 1
		while True:
			x = None
			if negl != []:
				x = negl.pop(0)
			elif posl != []:
				x = posl.pop(0)
			else:
				break
			if cnt[x] == 0:
				continue
			y = x * 2
			if y not in cnt:
				return False
			elif cnt[y] > 0 and cnt[x] > 0:
				cnt[y] = cnt[y] - 1
				cnt[x] = cnt[x] - 1
			else:
				return False
		return True


class Solution:

	def canReorderDoubled(self, A: List[int]) -> bool:
		seen = {}
		A.sort()
		for i in A:
			if i / 2 in seen:
				seen[i / 2] -= 1
				if seen[i / 2] == 0:
					del seen[i / 2]
			elif 2 * i in seen:
				seen[2 * i] -= 1
				if seen[2 * i] == 0:
					del seen[2 * i]
			elif i in seen:
				seen[i] += 1
			else:
				seen[i] = 1
		return not bool(seen)


class Solution:

	def canReorderDoubled(self, A: List[int]) -> bool:
		counter = Counter(A)
		for a in sorted(A, key=abs):
			if counter[a] == 0:
				continue
			if counter[2 * a] == 0:
				return False
			counter[a] -= 1
			counter[2 * a] -= 1
		return True


import collections

class Solution:

	def canReorderDoubled(self, a: List[int]) -> bool:
		count = collections.Counter(a)
		for elem in sorted(a, key=abs):
			if count[elem] == 0:
				continue
			if count[2 * elem] == 0:
				return False
			count[elem] -= 1
			count[2 * elem] -= 1
		return True


from collections import defaultdict

class Solution:

	def canReorderDoubled(self, A: List[int]) -> bool:
		if not A:
			return True
		count = 0
		d = defaultdict(int)
		for i in A:
			d[i] += 1
		for num in sorted(A):
			if num * 2 in d and d[num] and d[num * 2]:
				d[num] -= 1
				d[num * 2] -= 1
				count += 1
		return count == len(A) // 2


class Solution:

	def canReorderDoubled(self, A: List[int]) -> bool:
		negative = []
		positive = []
		zero_numbers = 0
		for a in A:
			if a < 0:
				negative.append(abs(a))
			elif a > 0:
				positive.append(a)
			else:
				zero_numbers += 1
		if zero_numbers % 2:
			return False
		negative.sort()
		positive.sort()
		return self.helper(negative) and self.helper(positive)

	def helper(self, nums):
		while nums:
			cur_num = nums[0]
			idx = self.binarySearch(nums, 2 * cur_num)
			if idx == -1:
				return False
			nums.pop(idx)
			nums.pop(0)
			if len(nums) == 1:
				return False
		return True

	def binarySearch(self, nums, key):
		head = 0
		tail = len(nums) - 1
		while head <= tail:
			mid = (head + tail) // 2
			if nums[mid] > key:
				tail = mid - 1
			elif nums[mid] < key:
				head = mid + 1
			else:
				return mid
		return -1


class Solution:

	def canReorderDoubled(self, A: List[int]) -> bool:
		count = collections.Counter(A)
		for a in sorted(count, key=lambda x: abs(x)):
			if count[a] > count[2 * a]:
				return False
			count[2 * a] -= count[a]
		return True


import numpy as np

class Solution:

	def canReorderDoubled(self, A: List[int]) -> bool:
		a = np.array(sorted(A))
		non_pos_idxs = np.where(a >= 0)[0]
		if len(non_pos_idxs) > 0:
			non_pos_idx = non_pos_idxs[0]
		else:
			non_pos_idx = len(a)
		b = a[:non_pos_idx][::-1]
		a = a[non_pos_idx:]
		if len(b) % 2 != 0:
			return False
		if not self.check_doubled(a):
			return False
		if not self.check_doubled(b):
			return False
		return True

	def check_doubled(self, a):
		if len(a) == 0:
			return True
		count_dict = {}
		for val in a:
			if count_dict.get(val, 0) > 0:
				count_dict[val] -= 1
			else:
				count_dict[2 * val] = count_dict.get(2 * val, 0) + 1
		for val in list(count_dict.values()):
			if val > 0:
				return False
		return True


class Solution:

	def canReorderDoubled(self, A: List[int]) -> bool:
		if not A:
			return True
		d = defaultdict(int)
		for x in A:
			d[x] += 1
		n = len(A) // 2
		A.sort()
		for x in A:
			if d[x] > 0:
				if 2 * x in d and d[2 * x] > 0:
					d[2 * x] -= 1
					d[x] -= 1
					n -= 1
					if n == 0:
						return True
		return False


class Solution:

	def canReorderDoubled(self, A: List[int]) -> bool:
		A.sort()
		d = collections.defaultdict(int)
		for a in A:
			if d[2 * a] > 0:
				d[2 * a] -= 1
			elif d[a / 2] > 0:
				d[a / 2] -= 1
			else:
				d[a] += 1
		return not any(d.values())


from collections import Counter

class Solution:

	def canReorderDoubled(self, A: List[int]) -> bool:
		counts = [0] * (10 ** 5 + 1)
		for a in A:
			if a >= 0:
				counts[a] += 1
		for i in range(10 ** 5 + 1):
			while counts[i] != 0:
				counts[i] -= 1
				if counts[i] < 0:
					return False
				counts[2 * i] -= 1
				if counts[2 * i] < 0:
					return False
		if not all((n == 0 for n in counts)):
			return False
		for a in A:
			if a < 0:
				counts[-a] += 1
		for i in range(10 ** 5 + 1):
			while counts[i] != 0:
				counts[i] -= 1
				if counts[i] < 0:
					return False
				counts[2 * i] -= 1
				if counts[2 * i] < 0:
					return False
		if not all((n == 0 for n in counts)):
			return False
		return True


class Solution:

	def canReorderDoubled(self, arr: List[int]) -> bool:
		dicti = dict()
		for var in arr:
			if var in list(dicti.keys()):
				dicti[var] += 1
			else:
				dicti[var] = 1
		arr.sort(key=lambda x: abs(x))
		for var in arr:
			if dicti[var] == 0:
				continue
			if 2 * var not in list(dicti.keys()):
				return False
			if dicti[2 * var] <= 0:
				return False
			dicti[var] -= 1
			dicti[2 * var] -= 1
		return True


class Solution:

	def get_result(self, sl, d):
		for k in sl:
			if d[k] == 0:
				continue
			if 2 * k not in d:
				return False
			v = d[k]
			v2 = d[2 * k]
			if v > v2:
				return False
			d[k] -= v
			d[2 * k] -= v
		return True

	def canReorderDoubled(self, A: List[int]) -> bool:
		d = dict()
		num_zeros = 0
		for a in A:
			if a == 0:
				num_zeros += 1
				continue
			if a in d:
				d[a] += 1
			else:
				d[a] = 1
		neg = [k for k in list(d.keys()) if k < 0]
		pos = [k for k in list(d.keys()) if k > 0]
		if num_zeros % 2 != 0:
			return False
		sorted_pos = sorted(pos)
		sorted_neg = sorted(neg, reverse=True)
		res = self.get_result(sorted_pos, d)
		if not res:
			return False
		res = self.get_result(sorted_neg, d)
		if not res:
			return False
		return sum(list(d.values())) == 0


class Solution:

	def canReorderDoubled(self, A: List[int]) -> bool:
		cnt = collections.Counter(A)
		for k in sorted(cnt, key=abs):
			if cnt[k] > cnt[2 * k]:
				return False
			cnt[2 * k] -= cnt[k]
		return True


class Solution:

	def canReorderDoubled(self, A: List[int]) -> bool:
		freq = dict()
		for i in A:
			freq[i] = freq.get(i, 0) + 1
		for k in sorted(list(freq.keys()), key=lambda x: abs(x)):
			if freq[k] == 0:
				continue
			if freq[k] > freq.get(2 * k, 0):
				return False
			freq[2 * k] -= freq[k]
		return True


from collections import Counter

class Solution:

	def canReorderDoubled(self, A: List[int]) -> bool:
		if not A:
			return True
		c = Counter(A)
		keys = sorted(c.keys())
		for k in keys:
			if k == 0:
				if c[k] % 2 == 0:
					c[k] = 0
				else:
					return False
			if k < 0 and c[k] > 0:
				if k / 2 in c:
					c[k / 2] -= c[k]
					c[k] = 0
			if k > 0 and c[k] > 0:
				if k * 2 in c:
					c[k * 2] -= c[k]
					c[k] = 0
		return set(c.values()) == {0}


class Solution:

	def canReorderDoubled(self, A: List[int]) -> bool:
		d = collections.Counter(A)
		if 0 in d:
			if d[0] & 1 == 1:
				return False
			d.pop(0)
		keys = sorted(d.keys())
		for i in keys:
			if i in d:
				if i < 0:
					if i / 2 not in d:
						return False
					if d[i] > d[i / 2]:
						return False
					d[i / 2] -= d[i]
					if d[i / 2] == 0:
						d.pop(i / 2)
					d.pop(i)
				else:
					if i * 2 not in d:
						return False
					if d[i] > d[i * 2]:
						return False
					d[i * 2] -= d[i]
					if d[i * 2] == 0:
						d.pop(i * 2)
					d.pop(i)
		return True


class Solution:

	def canReorderDoubled(self, A: List[int]) -> bool:
		A.sort()
		B = OrderedDict()
		for x in A:
			if x in B:
				B[x] += 1
			else:
				B[x] = 1
		while B:
			x = next(iter(B))
			freq = B.pop(x)
			if x < 0:
				if x % 2:
					return False
				if x // 2 not in B or B[x // 2] < freq:
					return False
				B[x // 2] -= freq
				if B[x // 2] == 0:
					B.pop(x // 2)
			elif x == 0:
				if freq % 2:
					return False
			else:
				if x * 2 not in B or B[x * 2] < freq:
					return False
				B[x * 2] -= freq
				if B[x * 2] == 0:
					B.pop(x * 2)
		return True


class Solution:

	def canReorderDoubled(self, A: List[int]) -> bool:
		c = collections.Counter(A)
		cc = sorted(c, key=abs)
		for x in cc:
			if c[x] > c[2 * x]:
				return False
			c[2 * x] -= c[x]
		return True


class Solution:

	def canReorderDoubled(self, A: List[int]) -> bool:
		neg = dict()
		pos = dict()
		zero = 0
		for n in A:
			if n < 0:
				if -n not in neg:
					neg[-n] = 0
				neg[-n] += 1
			elif n > 0:
				if n not in pos:
					pos[n] = 0
				pos[n] += 1
			else:
				zero += 1
		if zero % 2 != 0:
			return False

		def helper(nums):
			num_sorted = sorted(list(nums.keys()), reverse=True)
			while num_sorted:
				a = num_sorted.pop()
				if nums[a] == 0:
					continue
				if 2 * a not in nums or nums[a] > nums[2 * a]:
					return False
				nums[2 * a] -= nums[a]
			return True
		return helper(pos) and helper(neg)


from collections import defaultdict

class Solution:

	def canReorderDoubled(self, A: List[int]) -> bool:
		A.sort()
		s = defaultdict(int)
		for a in A:
			if a <= 0:
				if 2 * a in s:
					s[2 * a] -= 1
					if not s[2 * a]:
						del s[2 * a]
				else:
					s[a] += 1
			elif a % 2 == 0 and a // 2 in s:
				s[a // 2] -= 1
				if not s[a // 2]:
					del s[a // 2]
			else:
				s[a] += 1
		return not s


class Solution:

	def canReorderDoubled(self, A: List[int]) -> bool:
		hashtable = {}
		zero_count = 0
		for i in range(len(A)):
			if A[i] == 0:
				zero_count += 1
				continue
			if A[i] in list(hashtable.keys()):
				hashtable[A[i]] += 1
			else:
				hashtable[A[i]] = 1
		if zero_count % 2 == 1:
			return False
		else:
			key_list = []
			pair_count = 0
			for key in list(hashtable.keys()):
				key_list.append(key)
			key_list.sort()
			for key in key_list:
				if key % 2 == 0 and key // 2 in list(hashtable.keys()):
					m = min(hashtable[key], hashtable[key // 2])
					hashtable[key] -= m
					hashtable[key // 2] -= m
					pair_count += m
			if pair_count * 2 + zero_count == len(A):
				return True
			else:
				return False


from collections import Counter

class Solution:

	def canReorderDoubled(self, A: List[int]) -> bool:
		if not A:
			return True
		counts = Counter(A)
		for key in sorted(counts.keys()):
			if counts[key] == 0:
				continue
			factor = 0.5 if key < 0 else 2
			if counts[key] > counts[factor * key]:
				return False
			counts[factor * key] -= counts[key]
		return True


class Solution:

	def canReorderDoubled(self, A: List[int]) -> bool:
		D = {}
		for x in A:
			D[x] = D.get(x, 0) + 1
		D = dict([x for x in sorted(list(D.items()), key=lambda x: x[0])])
		for x in D:
			while D[x] > 0:
				D[x] -= 1
				if x <= 0:
					pair_x = x / 2
				else:
					pair_x = x * 2
				if D.get(pair_x, 0) > 0:
					D[pair_x] -= 1
				else:
					return False
		return True


class Solution:

	def canReorderDoubled(self, A: List[int]) -> bool:
		cnt = collections.Counter(A)
		for k in sorted(cnt, key=abs):
			a = cnt[k]
			if cnt[k] == 0:
				continue
			b = cnt.get(2 * k, 0)
			if b < a:
				return False
			cnt[2 * k] -= a
		return True


class Solution:

	def canReorderDoubled(self, A: List[int]) -> bool:

		def update_map(count, small, large):
			small_count = count[small]
			large_count = count[large]
			min_count = min(small_count, large_count)
			count[small] += -min_count
			if small != large:
				count[large] += -min_count
		if not A:
			return True
		element_count = {}
		ordered_elements = list(set(A))
		ordered_elements.sort()
		for number in A:
			if number not in element_count:
				element_count[number] = 0
			element_count[number] += 1
		for number in ordered_elements:
			number_count = element_count[number]
			double_number = number * 2
			if double_number in element_count:
				update_map(element_count, number, double_number)
		for number in element_count:
			if element_count[number] != 0:
				return False
		return True


from collections import Counter

class Solution:

	def canReorderDoubled(self, A: List[int]) -> bool:
		c = Counter(A)
		A = sorted(A)
		for (num, v) in sorted(list(c.items()), key=lambda item: item[0]):
			if num > 0 and c[num] > 0:
				if c[num] != 0 and c[num] > c[2 * num]:
					return False
				c[2 * num] -= c[num]
				c[num] = 0
			elif num < 0 and c[num] > 0:
				if num % 2 == 1:
					return False
				if c[num] != 0 and c[num] > c[num // 2]:
					return False
				c[num // 2] -= c[num]
				c[num] = 0
		return True


class Solution:

	def canReorderDoubled(self, A: List[int]) -> bool:
		if not A:
			return True
		positive_heap = []
		negative_heap = []
		zero = 0
		positive_d = defaultdict(int)
		negative_d = defaultdict(int)
		for i in A:
			if i == 0:
				zero += 1
			elif i < 0:
				heappush(negative_heap, -i)
				negative_d[-i] += 1
			else:
				heappush(positive_heap, i)
				positive_d[i] += 1
		if zero % 2 != 0:
			return False
		if not self.check(positive_heap, positive_d):
			return False
		if not self.check(negative_heap, negative_d):
			return False
		return True

	def check(self, h, d):
		for _ in range(len(h)):
			i = heappop(h)
			if d[i] == 0:
				continue
			if 2 * i not in d:
				return False
			elif d[2 * i] < d[i]:
				return False
			else:
				d[2 * i] -= d[i]
				d[i] = 0
		return True


class Solution:

	def canReorderDoubled(self, A: List[int]) -> bool:
		zcount = 0
		pos = []
		neg = []
		for n in A:
			if n == 0:
				zcount += 1
			elif n > 0:
				pos.append(n)
			else:
				neg.append(-n)

		def verifypos(A):
			count = collections.Counter(A)
			for x in sorted(A, key=abs):
				if count[x] == 0:
					continue
				if count[2 * x] == 0:
					return False
				count[x] -= 1
				count[2 * x] -= 1
			return True
		return verifypos(pos) and verifypos(neg)


class Solution:

	def canReorderDoubled(self, A: List[int]) -> bool:
		A.sort()
		dic = {}
		for i in A:
			if i % 2 == 0 and i / 2 in dic:
				i = i / 2
				dic[i] -= 1
				if dic[i] == 0:
					del dic[i]
			elif i * 2 in dic:
				i = i * 2
				dic[i] -= 1
				if dic[i] == 0:
					del dic[i]
			else:
				dic[i] = dic.setdefault(i, 0) + 1
				continue
		return len(dic) == 0


class Solution:

	def canReorderDoubled(self, A: List[int]) -> bool:
		A.sort()
		N = len(A)
		count = collections.Counter(A)
		for i in range(N):
			if A[i] == 0 or A[i] not in count:
				continue
			elif A[i] < 0:
				if A[i] % 2 == 1 or count[A[i] / 2] == 0:
					return False
				else:
					count[A[i] / 2] -= count[A[i]]
					if count[A[i] / 2] == 0:
						del count[A[i] / 2]
					del count[A[i]]
			elif count[A[i] * 2] == 0:
				return False
			else:
				count[A[i] * 2] -= count[A[i]]
				if count[A[i] * 2] == 0:
					del count[A[i] * 2]
				del count[A[i]]
		return True


class Solution:

	def canReorderDoubled(self, A: List[int]) -> bool:
		c = collections.Counter(A)
		for x in sorted(c):
			if c[x] == 0:
				continue
			if c[x] < 0:
				return False
			if x == 0:
				if c[x] % 2 != 0:
					return False
				else:
					continue
			if x > 0:
				temp = 2 * x
			elif x % 2:
				return False
			else:
				temp = x // 2
			if c[temp] < c[x]:
				return False
			else:
				c[temp] -= c[x]
		return True


class Solution:

	def canReorderDoubled(self, A: List[int]) -> bool:
		pos_set = set()
		neg_set = set()
		pos_dict = {}
		neg_dict = {}
		pos_count = 0
		for num in A:
			if num >= 0:
				pos_set.add(num)
				pos_dict[num] = 1 + pos_dict.get(num, 0)
				pos_count += 1
			else:
				neg_set.add(abs(num))
				neg_dict[abs(num)] = 1 + neg_dict.get(abs(num), 0)
		if pos_count % 2 != 0:
			return False
		else:
			return self.helper(pos_set, pos_dict) and self.helper(neg_set, neg_dict)

	def helper(self, set_, dict_):
		sorted_ = sorted(list(set_))
		for num in sorted_:
			if num * 2 in sorted_ and num != 0:
				small_ = dict_[num]
				large_ = dict_[num * 2]
				usage = min(small_, large_)
				dict_[num] -= usage
				dict_[num * 2] -= usage
			elif num == 0:
				if dict_[0] % 2 != 0:
					return False
				else:
					dict_[0] = 0
		for key in dict_:
			if dict_[key] != 0:
				return False
		return True


class Solution:

	def canReorderDoubled(self, A: List[int]) -> bool:
		c = Counter(A)
		for n in sorted(list(c.keys()), key=abs):
			while c[n] > 0 and c[(double := (2 * n))] > 0:
				c[n] -= 1
				c[double] -= 1
		return all((not v for v in list(c.values())))


class Solution:

	def canReorderDoubled(self, A: List[int]) -> bool:

		def factorize(num):
			power = 0
			while num % 2 == 0:
				(num, power) = (num // 2, power + 1)
			return (num, power)
		counts = defaultdict(lambda : [0] * 17)
		zeros = 0
		for a in A:
			if a == 0:
				zeros += 1
			else:
				(n, p) = factorize(a)
				counts[n][p] += 1
		if zeros % 2 == 1:
			return False
		for key in counts:
			carry = 0
			for p in counts[key]:
				carry = p - carry
				if carry < 0:
					return False
			if carry != 0:
				return False
		return True


class Solution:

	def canReorderDoubled(self, A: List[int]) -> bool:
		A.sort(key=lambda x: abs(x))
		c = {}
		for v in A:
			if v / 2 in c:
				c[v / 2] -= 1
				if not c[v / 2]:
					del c[v / 2]
			else:
				if v not in c:
					c[v] = 0
				c[v] += 1
		return len(c) == 0


import collections

class Solution:

	def canReorderDoubled(self, A: List[int]) -> bool:
		neg = collections.Counter()
		pos = collections.Counter()
		for n in A:
			if n >= 0:
				pos[n] += 1
			else:
				neg[n] += 1
		for n in sorted(neg, reverse=True):
			if neg[n * 2] < neg[n]:
				return False
			neg[n * 2] -= neg[n]
			del neg[n]
			if neg[n * 2] == 0:
				del neg[n * 2]
		if len(neg) != 0:
			return False
		for n in sorted(pos):
			if pos[n * 2] < pos[n]:
				return False
			pos[n * 2] -= pos[n]
			del pos[n]
			if pos[n * 2] == 0:
				del pos[n * 2]
		if len(pos) != 0:
			return False
		return True


class Solution:

	def canReorderDoubled(self, A: List[int]) -> bool:
		A.sort()
		freq = dict()
		for i in A:
			freq[i] = freq.get(i, 0) + 1
		for i in A:
			if freq.get(i, 0) == 0:
				continue
			if i < 0:
				if i % 2 != 0:
					return False
				elif not freq.get(i // 2, 0) > 0:
					return False
			elif i > 0 and (not freq.get(i * 2, 0) > 0):
				return False
			if i < 0:
				freq[i // 2] -= 1
			else:
				freq[i * 2] -= 1
			freq[i] -= 1
		return True


from collections import Counter

class Solution:

	def canReorderDoubled(self, A: List[int]) -> bool:
		negs = [a for a in A if a < 0]
		pos = [a for a in A if a > 0]
		zeros = [a for a in A if a == 0]
		if any(map(lambda x: len(x) % 2 != 0, [negs, pos, zeros])):
			return False
		if not self.is_valid(negs, True) or not self.is_valid(pos, False):
			return False
		return True

	def is_valid(self, A, neg=False):
		A = sorted(A)
		N = len(A)
		if neg:
			A = A[::-1]
		c = Counter(A)
		for a in A:
			if c[a] == 0:
				continue
			target = a * 2
			if c[target] == 0:
				return False
			c[a] -= 1
			c[target] -= 1
		return True


from collections import defaultdict

class Solution:

	def canReorderDoubled(self, A: List[int]) -> bool:
		A.sort()
		arr = defaultdict(int)
		for item in A:
			if 2 * item in arr and arr[2 * item] > 0:
				arr[2 * item] -= 1
			elif item % 2 == 0 and item // 2 in arr and (arr[item // 2] > 0):
				arr[item // 2] -= 1
			else:
				arr[item] += 1
		return sum([x for x in arr.values() if x != 0]) == 0


class Solution:

	def canReorderDoubled(self, A: List[int]) -> bool:
		table = collections.defaultdict(int)
		for num in A:
			table[num] += 1
		A.sort()
		for num in A:
			if table[num] == 0:
				continue
			pair = num * 2
			if num < 0:
				pair = num / 2
			if table[pair] < 1:
				return False
			table[num] -= 1
			table[pair] -= 1
		return True


class Solution:

	def canReorderDoubled(self, A: List[int]) -> bool:
		A = [abs(num) for num in A]
		A.sort()
		dic = collections.defaultdict(collections.deque)
		for (i, num) in enumerate(A):
			dic[num].append(i)
		visited = [0] * len(A)
		cnt = 0
		i = 0
		while i < len(A):
			if visited[i]:
				i += 1
				continue
			(val, val_double) = (A[i], 2 * A[i])
			if val_double in dic and dic[val_double]:
				if val not in dic or not dic[val]:
					return False
				dic[val].popleft()
				if not dic[val_double]:
					return False
				index = dic[val_double].popleft()
				visited[index] = 1
			else:
				return False
			i += 1
		return True


class Solution:

	def canReorderDoubled(self, A: List[int]) -> bool:
		counts = collections.Counter(A)
		count = 0
		A.sort()
		for num in A:
			if counts[num] and counts[num * 2]:
				counts[num * 2] -= 1
				counts[num] -= 1
				count += 1
		return count * 2 == len(A)


class Solution:

	def canReorderDoubled(self, A: List[int]) -> bool:
		counter = collections.Counter(A)
		for e in sorted(A, key=abs):
			if 2 * e in counter and counter[2 * e] > 0 and (counter[e] > 0):
				counter[e] -= 1
				counter[2 * e] -= 1
		print(counter)
		return sum(counter.values()) == 0


class Solution:

	def canReorderDoubled(self, A: List[int]) -> bool:
		A.sort()
		seen = Counter()
		for num in A:
			if num > 0 and num % 2:
				seen[num] += 1
				continue
			elem = 2 * num if num < 0 else num // 2
			if seen[elem] > 0:
				seen[elem] -= 1
			else:
				seen[num] += 1
		if sum(seen.values()):
			return False
		return True


from collections import Counter

class Solution:

	def canReorderDoubled(self, A: List[int]) -> bool:
		cnt = collections.Counter(A)
		for a in sorted(A, key=abs):
			if cnt[a] and cnt[a * 2]:
				cnt[a] -= 1
				cnt[a * 2] -= 1
		return all((cnt[a] == 0 for a in A))


import numpy as np

class Solution:

	def canReorderDoubled(self, A: List[int]) -> bool:
		A.sort()
		statdict = {}
		flag = True
		for i in A:
			if i in statdict:
				statdict[i] = statdict[i] + 1
			elif i < 0:
				if i * 2 in statdict:
					statdict[i * 2] = statdict[i * 2] - 1
					if statdict[i * 2] == 0:
						statdict.pop(i * 2)
				else:
					statdict[i] = 1
			elif i % 2 == 0 and i / 2 in statdict:
				statdict[int(i / 2)] = statdict[int(i / 2)] - 1
				if statdict[int(i / 2)] == 0:
					statdict.pop(int(i / 2))
			else:
				statdict[i] = 1
		return len(statdict) == 0 or (len(statdict) == 1 and 0 in statdict and (statdict[0] % 2 == 0))


class Solution:

	def canReorderDoubled(self, A: List[int]) -> bool:
		c = collections.Counter(A)
		for i in sorted(A, key=abs):
			if c[i] and c[i * 2]:
				c[i] -= 1
				c[i * 2] -= 1
		return all((c[i] == 0 for i in A))


class Solution:

	def canReorderDoubled(self, A: List[int]) -> bool:
		B = []
		for x in A:
			if x > 0:
				B.append(x)
			else:
				B.append(-x)
		count = collections.Counter(B)
		for x in sorted(B):
			if count[x] == 0:
				continue
			if count[2 * x] == 0:
				return False
			else:
				count[x] -= 1
				count[2 * x] -= 1
		return True


class Solution:

	def canReorderDoubled(self, A: List[int]) -> bool:
		D1 = collections.Counter()
		D2 = collections.Counter()
		zero = 0
		for a in A:
			if a < 0:
				D1[a] += 1
			else:
				D2[a] += 1
		for d in sorted(D1, reverse=1):
			if D1[d]:
				if D1[d * 2] < D1[d]:
					return False
				D1[d * 2] -= D1[d]
		for d in sorted(D2):
			if D2[d]:
				if D2[d * 2] < D2[d]:
					return False
				D2[d * 2] -= D2[d]
		return True


class Solution:

	def canReorderDoubled(self, A: List[int]) -> bool:
		n = len(A)
		neg = sorted(list([x for x in A if x < 0]))
		pos = sorted(list([x for x in A if x > 0]), reverse=True)
		(nl, pl) = (len(neg), len(pos))
		if nl % 2 or pl % 2:
			return False
		d1 = collections.Counter(neg)
		cnt = 0
		for i in range(nl):
			if d1[2 * neg[i]] > 0:
				d1[2 * neg[i]] -= 1
				d1[neg[i]] -= 1
				cnt += 1
		if cnt < nl // 2:
			return False
		d2 = collections.Counter(pos)
		cnt = 0
		for i in range(pl):
			if d2[2 * pos[i]] > 0:
				print((pos[i] * 2, pos[i]))
				d2[2 * pos[i]] -= 1
				d2[pos[i]] -= 1
				cnt += 1
		if cnt < pl // 2:
			return False
		return True


from collections import Counter

class Solution:

	def canReorderDoubled(self, A: List[int]) -> bool:
		A.sort()
		d = Counter()
		c = []
		e = []
		for i in A:
			if i < 0:
				c.append(i)
			elif i >= 0:
				e.append(i)
		c.sort(reverse=True)
		c.extend(e)
		A = c
		print(A)
		for i in A:
			d[i] += 1
		if d[0] % 2 != 0:
			return False
		d[0] = 0
		for i in A:
			if 2 * i in d and d[i] <= d[2 * i]:
				d[2 * i] -= d[i]
				d[i] = 0
			elif d[i] == 0:
				continue
			else:
				return False
		return True


from collections import Counter
from typing import List

class Solution:

	def canReorderDoubled(self, A: List[int]) -> bool:
		d = dict()
		num_zeros = 0
		for x in A:
			if x == 0:
				num_zeros += 1
				continue
			x = abs(x)
			y = x
			while y % 2 == 0:
				y //= 2
			if y in d:
				d[y].update([x])
			else:
				d[y] = Counter([x])
		if num_zeros % 2:
			return False
		for (base, counter) in d.items():
			keys = sorted(counter)
			for key in keys:
				if counter[key] <= counter[2 * key]:
					counter[2 * key] -= counter[key]
					counter[key] -= counter[key]
				else:
					return False
		return True


class Solution:

	def canReorderDoubled(self, A: List[int]) -> bool:
		counter = collections.Counter(A)
		counter = dict(sorted(counter.items(), key=lambda x: abs(x[0])))
		nums = []
		for num in counter.keys():
			for _ in range(counter[num]):
				nums.append(num)
		for num in nums:
			if counter[num]:
				if 2 * num in counter and counter[2 * num] != 0:
					counter[num] -= 1
					counter[num * 2] -= 1
				else:
					return False
		return True


class Solution:

	def canReorderDoubled(self, A: List[int]) -> bool:
		if len(A) == 0:
			return True
		mydict = {}
		for _ in range(0, len(A)):
			if A[_] in mydict:
				mydict[A[_]] += 1
			else:
				mydict[A[_]] = 1
		A_sorted = sorted(A)
		not_valid = set()
		for num in A_sorted:
			if len(mydict) == 0:
				return True
			if num in not_valid:
				continue
			if 2 * num in mydict and num in mydict:
				double = 2 * num
				mydict[num] -= 1
				mydict[double] -= 1
				if mydict[num] == 0:
					mydict.pop(num)
					not_valid.add(num)
				if num == double:
					continue
				elif mydict[2 * num] == 0:
					mydict.pop(2 * num)
					not_valid.add(2 * num)
			elif num / 2 in mydict and num in mydict:
				half = num / 2
				mydict[num] -= 1
				mydict[num / 2] -= 1
				if mydict[num] == 0:
					mydict.pop(num)
					not_valid.add(num)
				if mydict[num / 2] == 0:
					mydict.pop(num / 2)
					not_valid.add(num / 2)
			else:
				return False


class Solution:

	def canReorderDoubled(self, A: List[int]) -> bool:
		used = [False] * len(A)
		A.sort(key=lambda n: abs(n))
		bank = collections.Counter(A)
		for num in A:
			if bank[num] == 0:
				continue
			bank[num] -= 1
			if bank.get(2 * num, 0) == 0:
				return False
			bank[2 * num] -= 1
		return True


class Solution:

	def canReorderDoubled(self, A: List[int]) -> bool:
		c = collections.Counter(A)
		for k in sorted(c, key=abs):
			if c[k] > c.get(2 * k, 0):
				return False
			c[2 * k] -= c[k]
		return True


class Solution:

	def canReorderDoubled(self, A: List[int]) -> bool:
		st = {}
		A = sorted(A, reverse=True)
		for i in A:
			if i in st:
				st[i] += 1
			else:
				st[i] = 1
		for num in A:
			if num * 2 in st and st[num] > 0 and (st[num * 2] > 0):
				st[num * 2] -= 1
				st[num] -= 1
		for num in st:
			if st[num] > 0:
				return False
		return True


from collections import Counter

class Solution:

	def canReorderDoubled(self, A: List[int]) -> bool:
		count_a = Counter(A)
		A.sort(key=lambda x: abs(x))
		for elem in A:
			if count_a[elem] == 0:
				continue
			if count_a[elem * 2] == 0:
				return False
			count_a[elem] -= 1
			count_a[elem * 2] -= 1
		return True


class Solution:

	def canReorderDoubled(self, A: List[int]) -> bool:
		A.sort()
		map = {}
		for item in A:
			if item in map:
				map[item] += 1
			else:
				map[item] = 1
		for item in A:
			if map[item] == 0:
				continue
			if item < 0:
				if item / 2 in map:
					if map[item / 2] == 0:
						return False
					map[item] -= 1
					map[item / 2] -= 1
				else:
					return False
			elif item * 2 in map:
				if map[2 * item] == 0:
					return False
				map[item] -= 1
				map[item * 2] -= 1
			else:
				return False
		return True


class Solution:

	def canReorderDoubled(self, A: List[int]) -> bool:
		seen = dict()
		for x in A:
			if x not in seen:
				seen[x] = 0
			seen[x] += 1
		for x in sorted(seen, key=lambda x: x ** 2):
			if seen[x] == 0:
				continue
			if 2 * x not in seen or seen[x] > seen[2 * x]:
				return False
			else:
				seen[2 * x] -= seen[x]
		return True


from collections import Counter

class Solution:

	def canReorderDoubled(self, A: List[int]) -> bool:
		a = sorted(A, key=lambda x: abs(x), reverse=True)
		b = dict(Counter(A))
		while a:
			aa = a.pop()
			if aa in b:
				b[aa] -= 1
				if b[aa] == 0:
					del b[aa]
				if 2 * aa in b:
					b[2 * aa] -= 1
				else:
					return False
				if b[2 * aa] == 0:
					del b[2 * aa]
		return True


class Solution:

	def canReorderDoubled(self, A: List[int]) -> bool:
		d = {}
		for i in A:
			if i in d:
				d[i] += 1
			else:
				d[i] = 1
		A.sort()
		if 0 in d:
			if d[0] % 2 != 0:
				return False
			d.pop(0)
		for i in A:
			if i not in d:
				continue
			if i * 2 in d:
				if d[i] > d[i * 2]:
					d[i] -= d[i * 2]
					d[i * 2] = 0
				else:
					d[i * 2] -= d[i]
					d[i] = 0
				if d[i] == 0:
					d.pop(i)
				if d[i * 2] == 0:
					d.pop(i * 2)
			elif i % 2 == 0 and i // 2 in d:
				if d[i] > d[i // 2]:
					d[i] -= d[i // 2]
					d[i // 2] = 0
				else:
					d[i // 2] -= d[i]
					d[i] = 0
				if d[i] == 0:
					d.pop(i)
				if d[i // 2] == 0:
					d.pop(i // 2)
			else:
				return False
		return len(d) == 0


class Solution:

	def canReorderDoubled(self, A: List[int]) -> bool:
		A = sorted(A, key=lambda x: abs(x))
		M = Counter()
		for e in A:
			M[e] += 1
		for e in A:
			if M[e] and M[2 * e]:
				M[2 * e] -= 1
				M[e] -= 1
			elif M[e]:
				return False
		return True


class Solution:

	def canReorderDoubled(self, A: List[int]) -> bool:
		dic = collections.defaultdict(int)
		for i in range(len(A)):
			dic[A[i]] += 1
		ki = list(dic.keys())
		ki.sort(key=lambda x: abs(x))
		for k in ki:
			if dic[2 * k] < dic[k]:
				return False
			dic[2 * k] -= dic[k]
			dic[k] = 0
		return True