317. Can Everything Be Paired Off
Given n values and a number k, decide whether the values can be split into
n / 2 pairs so that EVERY pair sums to a multiple of k. Print yes or no.
Every value must be used exactly once, so an odd n is always no.
Trying pairings is factorial work. The whole question is decided by remainders,
because a sum is a multiple of k exactly when the two remainders add to k or
are both 0.
So count how many values fall in each remainder class and check three things:
remainder 0 must appear an even number of times, it pairs with itself
remainder k/2 only when k is even, also pairs with itself, so also even
remainder r must appear exactly as often as remainder k - r
The two self-pairing classes are the whole difficulty. Checking only the third rule accepts an array with three zeros, which cannot be paired at all.
Take the remainder carefully. In most languages -3 % 5 is -2 rather than 3,
so normalise with ((x % k) + k) % k before counting.
Constraints - `1 ≤ n ≤ 200000` - `1 ≤ k ≤ 1000000000` - `0 ≤ value ≤ 1000000000`
Input
The first line contains two integers n and k.
The second line contains n space-separated integers.
Output
Print yes if the values can be split into pairs each summing to a multiple of k, or no otherwise.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.