Pairing Array Elements for Divisible Sum

You are given an array of integers and an integer k. Your task is to determine whether the array can be divided into pairs such that the sum of every pair is divisible by k. Each element of the array must be used exactly once.

Note: If the array contains an odd number of elements, it is impossible to form pairs, and the answer is False.

The underlying logic is based on remainder arithmetic. For each number in the array, calculate its remainder modulo k. For a valid pairing, the following conditions must hold:

• The count of numbers with remainder 0 must be even.
• For every remainder r such that \(1 \le r \le k-1\), the number of elements with remainder \(r\) must equal the number of elements with remainder \(k - r\). When \(k\) is even, the number of elements with remainder \(\frac{k}{2}\) must also be even.

For example, if the input array is [1, 2, 3, 4, 5, 10] and k is 5, pairing is possible since:

• 1 + 4 = 5
• 2 + 3 = 5
• 5 + 10 = 15, and 15 is divisible by 5

Otherwise, if such pairing is not possible, output False.

Input Example in LaTeX Format:

\(n\) \(k\)
\(a_1\) \(a_2\) \(...\) \(a_n\)

inputFormat

The first line contains two integers n and k, where n is the number of elements in the array and k is the divisor. The second line contains n space-separated integers representing the array elements.

Constraints:

• \(1 \le n \le 10^5\)
• \(1 \le k \le 10^5\)
• \(-10^9 \le a_i \le 10^9\)

outputFormat

Output a single line: True if the array can be divided into pairs where the sum of each pair is divisible by k, and False otherwise.

## sample

6 5
1 2 3 4 5 10

True