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

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

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

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

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

 
Constraints:

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

Difficulty: interview

Starter code:

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

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

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

class Solution:
    def canArrange(self, arr: List[int], k: int) -> bool:
        if len(arr)==1:
            return False
        


        arr = collections.Counter(([i%k for i in arr]))

        if arr[0]%2 ==1:
            return False

        i = 1
        j = k - 1
        while i<=j:
            if i==j:
                if arr[i]%2==1:
                    return False

            if arr[i]!=arr[j]:
                return False
            i+=1
            j-=1

        return True
                
                


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


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


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


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



class Solution:
    def canArrange(self, arr: List[int], k: int) -> bool:
        '''
                ## APPROACH : 2 SUM ##
        ## LOGIC ##
\t\t## 1. Store the remainders in the hashmap and check if the current number has remaining remainder available in the hashset ##
        freq {remainder: remainder count}
        return true if not any of the pairs are true => we check if the freq[k-x%k]!=freq[x%k]. If we find any of such instance to be true, we return false
        
        '''
        freq = collections.Counter(map(lambda x: x%k, arr))
        return not any(val%2 if not key else val!=freq[k-key] for key,val in freq.items())

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


class Solution:
    def canArrange(self, arr: List[int], k: int) -> bool:
          m = {i:0 for i in range(k)}
          for a in arr:
            m[a%k] += 1

          for i in range(k):
            if i == 0:
              if m[i] % 2 != 0:
                return False
            elif m[i] != m[k-i]:
              return False

          return True


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

'''
现在需要把数组恰好分成 n / 2 对，以使每对数字的和都能够被 k 整除。
如果存在这样的分法，请返回 True ；否则，返回 False 。

思路：首先和得整除。要凑对，那就是mod能凑对，统计mod能否凑对即可
'''
class Solution:
    def canArrange(self, arr: List[int], k: int) -> bool:
        mod_count = [0 for i in range(k)]
        for i in arr:
            mod_count[i % k] += 1
        if mod_count[0] % 2:
            return False
        for i in range(1, len(mod_count)):
            if mod_count[i] != mod_count[k-i]:
                return False
        return True

# # O(nlogn)  S(n)
# class Solution:
#     def canArrange(self, arr: List[int], k: int) -> bool:
#         A = [a % k for a in arr]
#         A.sort()
#         l = 0
#         r = len(A) - 1
#         while l < len(A) and A[l] == 0:
#             l += 1
#         if l % 2 == 1:
#             return False
#         while l < r:
#             if A[l] + A[r] != k:
#                 return False
#             l += 1
#             r -= 1
#         return True
    
    
    
    
# O(n)  S(n)    
class Solution:
    def canArrange(self, arr: List[int], k: int) -> bool:
        c = collections.Counter([i%k for i in arr])
        for j in c:
            if j == 0:
                if c[j]%2!=0: return False
            else:
                if c[j]!=c[k-j]:return False
        return True

from collections import Counter

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

class Solution:
    def canArrange(self, arr: List[int], k: int) -> bool:
        
        #测试集不完整，可以通过，但是逻辑不对
        # return sum(arr) % k == 0
    
        
        nums = [i%k for i in arr]
        nums = [i for i in nums if i != 0]
        nums.sort()
        
        if len(nums) % 2 != 0:
            return False
        
        for i in range(len(nums)//2):
            if (nums[i] + nums[-1-i]) % k != 0:
                return False
        
        return True

import math

class Solution:
    def canArrange(self, arr: List[int], k: int) -> bool:
        # count of elements in each class
        moduloclasses = [0] * k
        for n in arr:
            moduloclasses[n % k] += 1
        
        # these two are 2*[n]=0
        # if there's a class in the middle
        # verify that it is even
        if k % 2 == 0 and moduloclasses[k//2] % 2 != 0:
            return False
        # modulo class for 0
        if moduloclasses[0] % 2 !=0:
            return False
        
        for i in range(1, math.ceil(k / 2)):
            # classes and their negatives
            if moduloclasses[i] != moduloclasses[k - i]:
                return False
        
        return True


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

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

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

class Solution:
    def canArrange(self, arr: List[int], k: int) -> bool:
        '''
        ex 1
        arr = [1,2,3,4,5,10,6,7,8,9], k = 5
        (2,8), (1,9), (3,7), (4,6), (5,10)
        return True
        
        ex 2
        arr = [1,2,3,4,5,6], k = 7
        (1,6), (2,5), (3,4)
        return True
        
        ex 3
        arr = [1,2,3,4,5,6], k = 10
        [1,2,3,5]
        (4,6), 
        return False
        
        ex 4
        arr = [-10,10], k = 2
        return True
        
        ex 5
        arr = [-1,1,-2,2,-3,3,-4,4], k = 3
        (-1,-2), (1,2), (-3,3), (-4,4)
        return True
        
        idea 1
        greedy, two pointers
        time - O(nlogn), space - O(n)
        '''
        arr_mod = [num % k for num in arr]
        arr_mod.sort()
        n = len(arr_mod)
        left, right = 0, n-1
        while left < n and arr_mod[left] == 0:
            left += 1
        if left % 2 != 0:
            return False
        while left < right:
            if arr_mod[left] + arr_mod[right] == k:
                left += 1
                right -= 1
            else:
                return False
        return True
        
        
        
        


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



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

from collections import defaultdict

class Solution:
    def canArrange(self, arr: List[int], k: int) -> bool:
        
        n: int = len(arr)
            
        # Get the modulus of each value
        # we want to combine the mods so that they equal the target
        mods = {ix: 0 for ix in range(k)}
        
        for val in arr:
            mods[val % k] += 1
        
        # Need pairs for 0 mod
        if mods[0] % 2 != 0:
            return False
        
        # We need an equal number of complimenting pairs for
        # each value
        for mod in range(1, k):
            
            comp = (k - mod)

            # print(f'mod: {mod}   comp: {comp}')
            # print(f'mods: {mods}')

            if mods[comp] != mods[mod]:
                return False                
    
        return True

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

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


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

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

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

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

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

                else:
                    return False
        return True

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


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


from collections import defaultdict

class Solution:
    def canArrange(self, arr: List[int], k: int) -> bool:
        counter = defaultdict(int)

        for n in arr:
            mod = n % k
            complement = (k - mod) % k
            if counter.get(complement, 0):
                counter[complement] -= 1
            else:
                counter[mod] += 1
        
        return all(v == 0 for v in counter.values())

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

            if arr[i]!=arr[j]:
                return False
            i+=1
            j-=1

        return True

class Solution:
    def canArrange(self, arr: List[int], k: int) -> bool:
        ## save remainder in hashmap and then check if remaining remainder is in the hashmap
        if len(arr)%2==1:
            return False
        mapping = defaultdict(int)
        count=0
        for i in arr:
            key = k-i%k
            
            if key in mapping and mapping[key] >=1:
                mapping[key]-=1
                count+=1
            else:
                mapping[(i%k) or k] +=1
                
            
            
        
        
                
        if count ==len(arr)//2:
            return True
        return False
                


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

from collections import defaultdict
class Solution:
    def canArrange(self, arr: List[int], k: int) -> bool:
        # ctr = set([])
        # for i in range(len(arr)):
        #     for j in range(i+1, len(arr)):
        #         if (arr[i] + arr[j]) % k == 0:
        #             if i in ctr or j in ctr:
        #                 continue
        #             else:
        #                 ctr.add(i)
        #                 ctr.add(j)
        # return len(ctr)/2 == len(arr)/2
        
        if len(arr) % 2 == 1:
            return False
        lookup = defaultdict(int)
        count = 0
        for idx, num in enumerate(arr):
            key = k - (num % k)
            if key in lookup and lookup[key] >= 1:
                count += 1
                lookup[key] -= 1
            else:
                lookup[(num % k) or k] += 1
        return count == len(arr)//2

from collections import Counter
class Solution:
    def canArrange(self, arr: List[int], k: int) -> bool:
        if len(arr) % 2 == 1: return False
        
        lookup = collections.defaultdict(int)
        count = 0
        for i, num in enumerate(arr):
            key = k - (num % k)
            if key in lookup and lookup[key] >= 1:
                # print(key, num)
                count += 1
                lookup[key] -= 1
            else:
                lookup[(num % k) or k] += 1
        return count == len(arr) // 2


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

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


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


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


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


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


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


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


from collections import Counter

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

class Solution:
    def canArrange(self, arr: List[int], k: int) -> bool:
        bag = {}
        for i in arr:
            if i < 0:
                i += ((-i) // k +1) * k
                
            r = i % k
            

            if r != 0:
                if k-r not in bag:
                    if r not in bag:
                        bag[r] = 0
                    bag[r] += 1
                else:
                    bag[k-r] -= 1
                    if bag[k-r] == 0:
                        del bag[k-r]
            else:
                if 0 in bag:
                    del bag[0]
                else:
                    bag[0]= 1
        return len(bag) == 0

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

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

class Solution:
    def canArrange(self, arr: List[int], k: int) -> bool:
        # int arr and integer k
        # divide array into pairs such that the sum of each pair is divisible by k
        # return True if possible, other false
        
        # [1, 2, 3, 4, 5, 10, 6, 7, 8, 9] k = 5   5, 10, 15, 20, 25, 30
        #  4  3  2
        #  9  8  7
        # 14 13 12
        # elem = 1 poss: 4, 9 k%5 == 4  
        # elem = 2 poss: 3, 8 k%5 == 3
        # elem = 3 poss: 2, 7 k%5 == 2
        # elem = 4 poss: 1, 6 k%5 == 1
        # elem = 5 poss: 10   k%5 == 0
        # elem = 6 poss: 4, 9
        # elem = 7 poss: 3, 8 # see if there are any pairs that have not been matched yet. if so, check their possible matches and see if one is available
        # elem = 8 poss: 2, 7
        # elem = 9 poss: 1, 6
        # elem = 10 poss: 5
        
        # arr = [1,2,3,4,5,6], k = 10
        # elem = 1 poss: x
        
        
        # 1 - 4 6 - 9 
        # 1 - 9 4 - 6
        
        # 2 - 3 8 - 7 
        # 2 - 8 3 - 7
        
        # 5 - 10
        modFrequencies = {}
        for i in range(0, len(arr)):
            difference = arr[i] % k
            if difference not in modFrequencies:
                modFrequencies[difference] = 0
            modFrequencies[difference] += 1
            
        for mod in modFrequencies:
            if mod == 0:
                if modFrequencies[mod] % 2 == 1: 
                    return False
            elif k-mod not in modFrequencies or modFrequencies[mod] != modFrequencies[k-mod]:
                return False
        return True
            
            
            
        


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

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


from collections import defaultdict
class Solution:
    def canArrange(self, arr: List[int], k: int) -> bool:
        '''
        x*k = num1 + num2 = a*k+remain1 + b*k+remain2
                        = (a+b)*k + remain1+remain2
                        remain1+remain2 = k,-k or 0
        
        
        [1,2,3,4,5,10,6,7,8,9]
        
        [1,2,3,4,0,0,1,2,3,4]
        '''
        
        d = defaultdict(int)
        for num in arr:
            sgn = 1 if num >= 0 else -1
            num = sgn*(abs(num)%k)
            if num==0:
                if d[0]:
                    d[0]-=1
                    if d[0]==0: del d[0]
                else:
                    d[0]+=1
            else:
                if -num in d and d[-num]:
                    d[-num]-=1
                    if d[-num]==0: del d[-num]
                elif -k-num in d and d[-k-num]:
                    d[-k-num]-=1
                    if d[-k-num]==0: del d[-k-num]
                elif k-num in d and d[k-num]:
                    d[k-num]-=1
                    if d[k-num]==0: del d[k-num]
                else:
                    d[num]+=1
        return len(d)==0

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

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


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

class Solution:
    def canArrange(self, arr: List[int], k: int) -> bool:
        
        modulo = [0]*k
        
        for a in arr:
            modulo[a%k] += 1
            
        # print(modulo)
        for i in range(1,k):
            if i == k-i and modulo[i] % 2 != 0:
                return False
            elif modulo[i] != modulo[k-i]:
                return False
        return True

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

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

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


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


from collections import Counter

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

class Solution:
    def canArrange(self, arr: List[int], k: int) -> bool:
        ## save remainder in hashmap and then check if remaining remainder is in the hashmap
        if len(arr)%2==1:
            return False
        mapping = defaultdict(int)
        count=0
        for i in arr:
            key = k-i%k
            print(key)
            if key in mapping and mapping[key] >=1:
                mapping[key]-=1
                count+=1
            else:
                mapping[(i%k) or k] +=1
                
            
            
        
        
                
        if count ==len(arr)//2:
            return True
        return False
                


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


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


from collections import Counter

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


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


class Solution:
    def canArrange(self, arr: List[int], k: int) -> bool:
        tmp = collections.Counter()
        for x in arr:
            tmp[x%k] += 1
        for c,v in list(tmp.items()):
            if c == 0 and v % 2 != 0:
                return False
            elif c != 0 and v != tmp[k-c]:
                return False
        return True
# class Solution:
#     def canArrange(self, arr: List[int], k: int) -> bool:
#         mod = [0] * k
#         for num in arr:
#             mod[num % k] += 1
#         print(mod)
#         if any(mod[i] != mod[k - i] for i in range(1, k // 2)):
#             return False
#         return mod[0] % 2 == 0

# 作者：LeetCode-Solution
# 链接：https://leetcode-cn.com/problems/check-if-array-pairs-are-divisible-by-k/solution/jian-cha-shu-zu-dui-shi-fou-ke-yi-bei-k-zheng-chu-/
# 来源：力扣（LeetCode）
# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。


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

from collections import Counter

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

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


class Solution:
    def canArrange(self, arr: List[int], k: int) -> bool:
        arr = sorted([c%k for c in arr])
        count = Counter(arr)
        # print(arr)
        # print(count)
        for i in range(len(arr)//2):
            if count[arr[i]] > 0:
                count[arr[i]]-=1
                if count[(k-arr[i])%k] == 0:
                    return False
                else:
                    count[(k-arr[i])%k]-=1
            
            # print(\"{0} => {1}\".format(arr[i], count))
        return True


class Solution:
    def canArrange(self, arr: List[int], k: int) -> bool:
        # Stores count of remainders
        c = collections.Counter([i%k for i in arr])
        
        for j in c:
            # If there is a reminder of 0 check that the number of times 0 occurs is even
            # THis guarantees pairing for the rest of remainders > 0
            if j == 0:
                if c[j]%2!=0: return False
            # If remainder is not 0
            # Check if the counts are even or have a pairing for remainders > 0
            else:
                if c[j]!=c[k-j]:return False
        return True

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

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

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

class Solution:
    def canArrange(self, arr: List[int], k: int) -> bool:
        #The idea is to count the residues
        
        #If every residue has the counter residue
        #such that x+y == k,then we found a pair
        
        count = [0]*k
        for num in arr:
            count[num%k] +=1
        
        #Now since we have 0,1,2,.....k-1 as residues
        #If count[1] == count[k-1],pairs+=count[0]  
        print('count ',count)
        for x in range(k):
            comp = -x % k 
            # x+comp = 0 mod k, or
            # (x+comp) mod k = 0
            print('Comp : ',comp)
            while count[x]>0:
                count[x]-=1
                count[comp]-=1
                if count[comp]<0:
                    return False
        
        return True

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

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


class Solution:
    def canArrange(self, arr: List[int], k: int) -> bool:
        
        n = len(arr)
        mod_count = [0 for i in range(0,k)]
        
        
        for i in range(0,n):
            mod_count[arr[i]%k]+=1
            
            
        #print(mod_count)
        
        mid = int(k/2)
        #print(\"mid = %d\" %mid)
        
        if(k%2==1):     #odd bucket [0], [1,k-1], [2,k-1], ...[mid-1,mid+1]
            if(mod_count[0]%2==1):
                #print(\"debug0\")
                return False
        else:           #even bucket [0], [1,k-1], [2,k-2], ...[mid]
            if(mod_count[0]%2==1 or mod_count[mid]%2==1):
                #print(\"debug1\")
                return False

        num = int((k-1)/2)
        
        for i in range(1,num+1):
            #print(i,k-1-i)
            if(mod_count[i]!=mod_count[k-i]):
                #print(\"debug2\")
                return False
        
        return True

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


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

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

        if len(pairs) == n // 2:
            return True
        
        else:
            return False


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

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

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

class Solution:
    def canArrange(self, arr: List[int], k: int) -> bool:
        count = [0]*k
        for num in arr:
            count[num%k] +=1
        
        #Now since we have 0,1,2,.....k-1 as residues
        #If count[1] == count[k-1],pairs+=count[0]  
        print(count)
        for x in range(k):
            comp = -x % k 
            # x+comp = 0 mod k, or
            # (x+comp) mod k = 0
            print(comp)
            while count[x]>0:
                count[x]-=1
                count[comp]-=1
                if count[comp]<0:
                    return False
        
        return True

class Solution:
    def canArrange(self, arr: List[int], k: int) -> bool:
        # 余数字典
        d = {i:0 for i in range(k)}
        # 求每个值的余数，并统计个数
        for num in arr:
            d[num % k] += 1
        # 若正好除尽的个数为奇数，证明除不尽的为奇数个，无法形成pair
        if d[0] % 2 != 0:
            return False
        for i in range(1, k):
            # 此处有一个trick，若两个数余数相加为k,则这两个数的和可以被k整除（相当于多加了一个k），所以如果出现频率相等，这两组数即可两两配对
            if i != k-i:
                if d[i] != d[k-i]:
                    return False
            else:
                if d[i] % 2 != 0:
                    return False
        
        return True

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


from collections import Counter

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


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

class Solution:
    def canArrange(self, arr: List[int], k: int) -> bool:
        '''
        # Note:
            the arr's length is even
        # Notes:
            each pair has two numbers
            get the remainder of each number divided by k
        '''
        n = len(arr)
        for i in range(n):
            arr[i] = arr[i] % k
        lookup = defaultdict(int)
        for i in range(n):
            if not arr[i]:
                continue
            if k - arr[i] in lookup:
                lookup[k-arr[i]] -= 1
                if not lookup[k-arr[i]]:
                    lookup.pop(k-arr[i])
            else:
                lookup[arr[i]] += 1

        if not lookup:
            return True
        return False

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


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

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


class Solution:
    def canArrange(self, arr: List[int], k: int) -> bool:
        # Stores count of remainders
        c = collections.Counter([i%k for i in arr])
        
        for j in c:
            # If reminder is 0
            # Check if this remainder is even
            if j == 0:
                if c[j]%2!=0: return False
            # If remainder is not 0
            # Check if current remainder c[j] is not equal to c[k-j], divisor-current remainder
            else:
                if c[j]!=c[k-j]:return False
        return True

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

import collections as clc


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

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