Given an integer array arr of length n and an integer k, determine whether it is possible to partition arr into exactly $\frac{n}{2}$ disjoint pairs such that, for every pair, the sum of the two elements is divisible by k. Return true if such a pairing exists, otherwise return false.

Constraints:

• arr.length == n

• $1 \leq `n` \leq 10^5$

• n is even

• $-10^9 \leq `arr[i]` \leq 10^9$

• $1 \leq `k` \leq 10^5$

Now, let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Implement your solution in the following coding playground.