1497. Check If Array Pairs Are Divisible by k - Detailed Explanation

Problem Statement

Given an array of integers arr of even length and an integer k, determine whether it is possible to rearrange the array into pairs such that the sum of each pair is divisible by k. In other words, for each pair (a, b) formed from the elements of arr, the condition

(a + b) % k == 0

must hold.

Example 1

• Input: arr = [9, 7, 5, 3], k = 6
• Output: true
• Explanation: One way to form the pairs is (9, 3) and (7, 5). Their sums are 12 and 12 respectively, and since 12 % 6 = 0, the condition is satisfied.

Example 2

• Input: arr = [92, 75, 65, 48, 45, 35], k = 10
• Output: true
• Explanation: The remainders when dividing by 10 are:
  • 92 % 10 = 2
  • 75 % 10 = 5
  • 65 % 10 = 5
  • 48 % 10 = 8
  • 45 % 10 = 5
  • 35 % 10 = 5
    Here, one possible pairing is to pair the element with remainder 2 (92) with the element with remainder 8 (48), and pair the remaining ones (all with remainder 5) among themselves. Notice that when k is even, the numbers that give a remainder of k/2 (in this case, 5) must have an even count.

Example 3

• Input: arr = [1, 2, 3, 4, 5, 6], k = 10
• Output: false
• Explanation: The remainders are 1, 2, 3, 4, 5, 6. For a valid pairing, every remainder r should have a matching count equal to the count of remainder (k - r). Here, there is no remainder 9 to pair with remainder 1 (since 1 + 9 = 10) and similarly for other unmatched values, so it is impossible to form valid pairs.

Constraints:

• The length of arr is even.
• 1 ≤ arr.length ≤ 10⁵
• -10⁵ ≤ arr[i] ≤ 10⁵
• 1 ≤ k ≤ 10⁵

Hints

1. Modulo Analysis:
   Instead of working with the actual numbers, compute the remainder of each element when divided by k (i.e., num % k). Numbers can be grouped by these remainders.

2. Pairing Conditions:
   For the pairing to be possible:

   • All elements with remainder 0 must appear an even number of times.
   • For any remainder r (where 1 <= r < k), the count of r should equal the count of k - r.
   • If k is even, elements with remainder k/2 must also appear an even number of times because k/2 + k/2 = k.

Approaches

Approach 1: Remainder Frequency Counting

Explanation

1. Compute Remainder Frequencies:

   • Traverse the array and compute remainder = num % k for each number. (If handling negatives, adjust the remainder so it lies in the range [0, k–1].)
   • Use a hash map (or array of size k) to count the frequency of each remainder.

2. Check for Valid Pairs:

   • If the remainder is 0, ensure that its count is even.
   • For remainders r from 1 to k-1, check whether the frequency of r equals the frequency of k - r.
   • For the special case where k is even, verify that the count of elements with remainder k/2 is even.

3. Return Result:
   If all the above conditions are met, then it is possible to rearrange the array into valid pairs; otherwise, it is not.

Complexity Analysis

• Time Complexity: O(n), where n is the size of arr (we perform one pass to count remainders and another pass over possible remainders up to k).
• Space Complexity: O(k), for storing the frequency counts.

Approach 2: Two-Pass Verification

A similar method involves two passes:

1. In the first pass, compute and store the frequencies of all remainders.

2. In the second pass, iterate over the possible remainders from 0 to k/2 and check the required conditions for valid pairing.

This approach essentially follows the same idea as Approach 1 with slightly different implementation details.

Code Solutions

Python Implementation