1497. Check If Array Pairs Are Divisible by k

Problem Statement

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.

Constraints:

arr.length == n
1 <= n <= 105
n is even.
-109 <= arr[i] <= 109
1 <= k <= 105

Intuition

Calculate the Remainder of each element with k

So each element will be mapped in range of 0 to k-1,
So remainder 1 will be paired with k-1, 2 with k-2 to make pair

and 0 rem count will be paired with 0

So just check count of all this

Video Links

Approach 1:

C++

class Solution {
public:
    bool canArrange(vector<int>& arr, int k) {
        vector<int> rem(k, 0);
        for(auto &it: arr){
            int x = ((it%k) + k)%k;
            rem[x] ++;
        }

        for(int i=1; i<=k/2; i++){
            if(rem[i] != rem[k-i]){
                return false;
            }
        }

        if(rem[0]%2)
            return false;
        
        return true;
    }
};

Approach 2:

C++

Approach 3:

C++

Approach 4:

C++