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.

&nbsp;
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.


&nbsp;
Constraints:


	arr.length == n
	1 &lt;= n &lt;= 105
	n is even.
	-109 &lt;= arr[i] &lt;= 109
	1 &lt;= k &lt;= 105


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[1]
        #since we have odd number of complimenting residues,
        #we should also care about residue=0 and residue=k//2
        
        i,j =1,k-1
        pairs  = 0
        while i<j :
            if count[i]!=count[j]:
                return False
            pairs += count[i]
            i+=1
            j-=1
        if pairs>0 and i==j:
            pairs+=count[i]/2
        pairs+= count[0]/2
        n = len(arr)
        return pairs == n//2
class Solution {
    public boolean canArrange(int[] arr, int k) {
        int[] frequency = new int[k];
        for(int num : arr){
            num %= k;
            if(num < 0) num += k;
            frequency[num]++;
        }
        if(frequency[0]%2 != 0) return false;
        
        for(int i = 1; i <= k/2; i++)
            if(frequency[i] != frequency[k-i]) return false;
			
        return true;
    }
}
//ask the interviewer
//can we have negative values?

class Solution {
public:
    bool canArrange(vector<int>& arr, int k)
    {
        unordered_map<int,int>memo;//remainder : occurence

        //we are storing the frequency of curr%k
        //i.e. the frequency of the remainder
        for(auto curr : arr)
        {
            int remainder = ((curr%k)+k)%k;
            memo[remainder]++;
        }

        for(int i =1; i<=k/2; i++)
        {
            if(memo[i] != memo[k-i])
                return false;
        }
        if(memo[0]%2 != 0)
            return false;
        return true;
    }
};
var canArrange = function(arr, k) {
    let map = new Map();
    let index = 0;
    for(let i = 0; i < arr.length; i++){
        let val = arr[i] % k;
        if(val<0) val+=k;
        if(map.get(k-val)) map.set(k-val, map.get(k-val) - 1), index--;
        else if(map.get(-val)) map.set(-val, map.get(-val) - 1), index--;
        else map.set(val, map.get(val) + 1 || 1), index++;
    }
    return !index;
};
Check If Array Pairs Are Divisible by k