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

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

class Solution:
    def canReorderDoubled(self, A: List[int]) -> bool:
        cache=collections.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:
        ''' Place all values into dicts and start counting from the bottom
        '''
        if not A:
            return True
        
        pos = collections.defaultdict(int)
        neg = collections.defaultdict(int)
        zero = 0
        
        # O(n)
        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):
        
        # worst case O(n), done n times
        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:
        ''' Place all values into dicts and start counting from the bottom
        '''
        if not A:
            return True
        
        pos = {}
        neg = {}
        zero = 0
        
        # O(n)
        for v in A:
            if v > 0:
                pos[v] = pos.get(v, 0) + 1
            if v < 0:
                neg[-v] = neg.get(-v, 0) + 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):
        
        # worst case O(n), done n times
        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:
                # print(f\"checking {num}\")
                double = num * 2
                # print(half, double)

                if double in count and count[double] > 0:
                    # print(\"found\", double)
                    count[num] -= 1                    
                    count[double] -= 1
                    # print(count)
                    # print(\"all good\")
        # print(count)     
        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:
        ''' Place all values into dicts and start counting from the bottom
        '''
        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

import collections

class Solution:
    def canReorderDoubled(self, A: List[int]) -> bool:
        ''' Place all values into dicts and start counting from the bottom
        '''
        if not A:
            return True
        
        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:
        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
                        # break
            else:
                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
                    # Break
        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:
        pos = [x for x in A if x >= 0]
        neg = [x for x in A if x < 0]
        for L in (pos,neg):
            count = collections.Counter(L)
            for x in sorted(L, 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:
        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)
            else:
                if posl != [] :
                    x = posl.pop(0)
                else:
                    break
            if cnt[x] == 0 :
                continue
            y = x * 2
            if y not in cnt:
                return False
            else:
                if 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:
            #Logic for checking half and double of number
            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]
            else:
                if 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:
        # Eliminate zero
        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()
        # print(negative, positive)
        
        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)
            # print('helper',nums[0], idx)
            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
        # print(nums, key)
        
        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:
        seen = {}
        A.sort()
        for ind,i in enumerate(A):
            #Logic for checking half and double of number
            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]
            else:
                if i in seen:
                    seen[i] += 1
                else:
                    seen[i] = 1
        
        print(seen)
        
        return not bool(seen)

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
            #print(x,d,n)
        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)
        # It handles the case where there is odd number of 0, since the total number is even, there should be a number which cannot match because of the extra 0
        for k in sorted(cnt, key=abs):
            if cnt[k] > cnt[2*k]:
                return False
            
            cnt[2*k] -= cnt[k]
            
        return True

from collections import Counter

class Solution:
    def canReorderDoubled(self, A: List[int]) -> bool:
        # Greedy
        # Time  complexity: O(NlogN)
        # Space complexity: O(N)
        # count = 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


        count = Counter(A)
        for x in sorted(count, key=abs):
            if count[x] > count[2 * x]:
                return False
            count[2 * x] -= count[x]
        return True


class Solution:
    def canReorderDoubled(self, A: List[int]) -> bool:
        count = collections.Counter(A)
        for i in sorted(count, key=abs):
            count[2*i] -= count[i]
            if count[2*i] < 0:
                return False
        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:
        cache=collections.Counter(A)
        c_list=sorted(list(cache),key=lambda x: (abs(x),x))
        for x in c_list:
            if cache[x]>cache[2*x]:
                return False
            cache[2*x]-=cache[x]
        return True

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)
            
            #print(x,freq)
            
            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)
        #print(cc)
        for x in cc:
            #print(str(x), end=\": \")
            #print(c)
            if c[x] > c[2 * x]:
                return False
            c[2 * x] -= c[x]
        #print(c)
        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
        #print(pos,neg)
        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
            else:
                if 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:
        # O(NlogN) time        
        # O(N) space
        
        if not A:
            return True
        
        counts = Counter(A)        
        
        for key in sorted(counts.keys()):
            if counts[key] == 0:
                continue
            
            factor = .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:
        A.sort(key=lambda x: abs(x))
        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


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:
        count = collections.Counter(A)
        for x in sorted(A, key=abs):
            if count[x] == 0:
                continue
            if x == 0 and x % 2:
                return False
            if count[x] > count[2 * x]:
                return False
            count[x], count[2 * x] = 0, count[2 * x] - count[x]
        
        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([kv for kv 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:
        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:
        # https://blog.csdn.net/fuxuemingzhu/article/details/84925747
        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]]
            else:
                if 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
                


from collections import Counter
class Solution:
    def canReorderDoubled(self, A: List[int]) -> bool:
        if not A: return True
        C = Counter(A)
        K = sorted(C.keys())
        for k in K:
            if k == 0:
                if C[k] & 1:
                    return False
                else:
                    C[k] = 0
            if k < 0 and C[k] > 0:
                if k % 2 == 0 and (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:
        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:
        # https://www.cnblogs.com/seyjs/p/10092569.html
        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(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:
        
        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:
        count = Counter(A)
        for x in sorted(A, key = abs):
            if count[x]==0: continue # x may be end of a pair
            if count[2*x]==0: 
                return False # x exsist, we have to match it with a 2x
            count[2*x] -= 1
            count[x] -= 1
        return True

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
        
        '''
        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:
        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:
        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:
        
        
        ## Time Complexity: O(N LOG N) , Space: O(N)
        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:
        count = 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:
        # Array of Doubled Pairs 9/24 8/31/20
        # 1:43 9/1/2020
#         c = collections.Counter(A)
#         for x in sorted(c, key=abs):
#             if c[x] > c[x * 2]:
#                 return False
#             c[x*2] -= c[x]
        
#         return True
        

    
        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 cnt < len(A) // 2 :
        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
            # cnt += 1
            
        return True
    
#         A = [abs(num) for num in A ]
#         A.sort()
#         dic = collections.defaultdict(int)
#         for num in A:
#             dic[num] += 1
        
#         visited = [0]*len(A)
#         cnt = 0
#         i = 0
#         while cnt < len(A) // 2 :
#             if visited[i]:
#                 i += 1
#                 continue
#             val_small = A[i]
#             if 2*val_small in dic:
#                 dic[2*val_small] -= 1
#                 dic[val_small] -= 1
#                 if dic[2*val_small] < 0 or dic[val_small] < 0:
#                     return False
#                 search_index = A.index(2*val_small, i+1)
#                 while visited[search_index]:
#                     search_index = A.index(2*val_small, search_index+1)
#                 visited[search_index] = 1
#             else:
#                 return False
#             i += 1
#             cnt += 1
            
#         return True
                

            
        


class Solution:
    def canReorderDoubled(self, A: List[int]) -> bool:
        counts = collections.Counter(A)
        count = 0
        A.sort()
        for num in A: #range(0,len(A)//2):
            #num = A[i] 
            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:
        # if len(A)%2==1:
        #     return False
        # counter = Counter(A)
        # # print(counter)
        # Skey = set(counter.keys())
        # key = counter.keys()
        # for i in key:
        #     if 2*i in Skey:
        #         counter[i]=0
        #         counter[i*2]-=counter[i]
        # val = list(counter.values())
        # print(val)
        # for i in val:
        #     if i !=0:
        #         return False
        # return True
        
        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)

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

import numpy as np

class Solution:
    def canReorderDoubled(self, A: List[int]) -> bool:
        A.sort()
        statdict = {}
        flag = True
#        print(A)
        for i in A:
#            print(statdict)
            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
            else:
                if (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)
        #A[2*i+1] = 2*A[2*i]
        #[-2,-4,2,4]
        #A[1] == 2*A[0]
        #A[3] == 2*A[2]
        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    


class Solution(object):
    def canReorderDoubled(self, 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

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:
        c=collections.Counter(A)
        
        for x in sorted(A,key=abs):
            if c[x]==0:
                continue
            if c[2*x]==0:
                return False
            c[x]-=1
            c[2*x]-=1
        return True


# 20201007 12:08 选参考答案
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

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:
        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:
        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)
        
        #print(A_sorted)
        #print(mydict)
        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)
                #deals with duplicates
                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:
        
        # Divide an conquer
        # Sort items according to their magnitude
        # For each item, make sure it's double exists later in the list
        # When a double is used, mark it with a mask
        
        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
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            


from collections import Counter

class Solution:
    def canReorderDoubled(self, A: List[int]) -> bool:
        # Greedy
        # Time  complexity: O(NlogN)
        # Space complexity: O(N)
        count = 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:
        A_sorted = sorted(A, key=abs)
        count = collections.Counter(A)
        for a in A_sorted:
            if count[a] == 0: 
                continue
            if count[a * 2] == 0:
                return False
            count[a] -= 1
            count[a * 2] -= 1
            
        return True

class Solution(object):
    def canReorderDoubled(self, 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


class Solution(object):
    def canReorderDoubled(self, 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


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
        #print(st)
        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
            #print(num,st)
        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:
        count = collections.Counter(A)
        for x in sorted(A, key = abs):
            if count[x] == 0:
                continue
            if count[x*2] == 0:
                return False
            count[x] -= 1
            count[2*x] -= 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
            else :
                if 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


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

        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:
        
        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:
        counter = collections.Counter(A)
        for x in sorted(counter,key=abs):
            if counter[x] > counter[2*x]:
                return False
            counter[2*x] -= counter[x]
        return True    

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:
                    # print(\"found\", double)
                    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:
        c = collections.Counter(A)
        for x in sorted(c, key=abs):
            if c[x] > c[2 * x]:
                return False
            c[2 * x] -= c[x]
        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:
            #print(i,d)
            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


import collections

class Solution:
    def canReorderDoubled(self, A: List[int]) -> bool:
        ''' Place all values into dicts and start counting from the bottom
        '''
        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:
        A = sorted(A, key=lambda x: abs(x))
        M = Counter()
        
        for e in A:
            M[e] += 1
        
        # print(M)
        # print(A)
        
        for e in A:
            # print(e, M[2*e], M)
            if M[e] and M[2*e]:
                M[2*e] -= 1
                M[e] -= 1
                # print('->', 2*e, M[2*e])
            elif M[e]:
                # print(M, e)
                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:
        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