Check If Array Pairs Are Divisible by k

Leetcode Problem:

• Check If Array Pairs Are Divisible by k

Summary

• Given an array of integers and an integer k, determine if it is possible to divide the array into exactly n/2 pairs such that the sum of each pair is divisible by k.

Approach

• This problem can be solved using a hash map to count the remainders of the array elements when divided by k
• We first calculate the offset as k * k, then for each number in the array, we increment the count of the remainder
• If the count of 0 is odd, it means that we cannot divide the array into pairs with sum divisible by k
• Otherwise, we check if the counts of all remainders from 1 to k-1 are equal, and if the count of k/2 is odd when k is even
• If any of these conditions are not met, we return false
• Otherwise, we return true.

Complexity

• O(n) where n is the length of the array

Explain

• This solution works by first calculating the offset as k * k, then for each number in the array, we increment the count of the remainder
• If the count of 0 is odd, it means that we cannot divide the array into pairs with sum divisible by k
• Otherwise, we check if the counts of all remainders from 1 to k-1 are equal, and if the count of k/2 is odd when k is even
• If any of these conditions are not met, we return false
• Otherwise, we return true.

Solution Code:

class Solution {
public:
    unordered_map cnt;
    bool canArrange(vector& arr, int k) {
        if (k == 1) return true;
        long long offset = k;
        while(offset < 1e9){
            offset *= k;
        }
        for(long long num : arr){
            cnt[(num + offset) % k]++;
        }
        if(cnt[0] & 1) return false;
        for(int i = 1; i < ((k+1)>>1); i++){
            if(cnt[i] != cnt[k - i]) return false;
        }
        if((k %2) == 0 && ((cnt[k/2] %2) == 1)){
            return false;
        }
        return true;
    }
};