Given an integer array arr of length n and an integer k, determine whether it is possible to partition arr into exactly 2n 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≤‘n‘≤105
n is even
−109≤‘arr[i]‘≤109
1≤‘k‘≤105
Input: arr = [2, 11, 4, 9, 7, 6]-List[int], k = 13-int
Output: true-bool
Explanation: The remainders mod 13 are [2, 11, 4, 9, 7, 6]. Valid complementary pairs must sum to 13 in remainder space, (2,11), (4,9), and (7,6), so all elements can be paired and a full partition exists.
Input: arr = [1, 2, 3, 4, 5, 6, 7, 8]-List[int], k = 9-int
Output: true-bool
Explanation: The remainders mod 9 are the same as the values. Pairing each remainder r with 9-r gives (1,8), (2,7), (3,6), and (4,5), so every element is used exactly once and each pair sums to a multiple of 9.
Input: arr = [-1, -2, -3, -4, 1, 2, 3, 4]-List[int], k = 5-int
Output: true-bool
Explanation: Normalizing remainders to [0, k-1] gives -1→4, -2→3, -3→2, -4→1, 1→1, 2→2, 3→3, and 4→4. The counts match for complementary remainders (1 pairs with 4, and 2 pairs with 3), so we can form pairs like (-4,4), (-3,3), (-2,2), and (-1,1), each summing to a multiple of 5.
Input: arr = [0, 0, 0, 0, 5, 10, 15, 20]-List[int], k = 5-int
Output: true-bool
Explanation: Every element is divisible by 5, so every remainder is 0. Elements with remainder 0 can pair among themselves, and since there are 8 such elements (an even count), we can partition them into 4 valid pairs.
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: