Check If Array Pairs Are Divisible by k

medium hash map modular arithmetic

Problem

You are given an integer array arr whose length n is even, and a positive integer k. Decide whether the whole array can be split into exactly n / 2 pairs so that the sum of every pair is divisible by k. Each element must belong to exactly one pair, and values may be negative.

Return true if such a complete pairing exists, otherwise false.

Inputarr = [1,2,3,4,5,10,6,7,8,9], k = 5

Outputtrue

Pairs (1,9), (2,8), (3,7), (4,6), (5,10) each sum to a multiple of 5.

arr (comma-separated, even count)

def can_arrange(arr, k):
    count = [0] * k
    for x in arr:
        count[x % k] += 1   # Python % is already non-negative
    if count[0] % 2 != 0:
        return False
    for r in range(1, k // 2 + 1):
        if count[r] != count[k - r]:
            return False
    return True

function canArrange(arr, k) {
  const count = new Array(k).fill(0);
  for (const x of arr) {
    count[((x % k) + k) % k]++;
  }
  if (count[0] % 2 !== 0) return false;
  for (let r = 1; r <= Math.floor(k / 2); r++) {
    if (count[r] !== count[k - r]) return false;
  }
  return true;
}

boolean canArrange(int[] arr, int k) {
    int[] count = new int[k];
    for (int x : arr) {
        count[((x % k) + k) % k]++;
    }
    if (count[0] % 2 != 0) return false;
    for (int r = 1; r <= k / 2; r++) {
        if (count[r] != count[k - r]) return false;
    }
    return true;
}

bool canArrange(vector<int>& arr, int k) {
    vector<int> count(k, 0);
    for (int x : arr) {
        count[((x % k) + k) % k]++;
    }
    if (count[0] % 2 != 0) return false;
    for (int r = 1; r <= k / 2; r++) {
        if (count[r] != count[k - r]) return false;
    }
    return true;
}

Explanation

The key insight is that whether a + b is divisible by k depends only on the remainders of a and b mod k: the sum is divisible exactly when the two remainders add up to 0 or to k. So the actual values do not matter at all — only how many elements fall into each remainder class.

We tally those classes in a frequency table count of size k (an array works as a perfect hash map here, since keys are exactly 0..k-1). One subtlety: in JavaScript, Java, and C++ the % operator can return a negative result, so we normalize with ((x % k) + k) % k; Python's % is already non-negative.

Then the pairing rules fall out of the math. Elements with remainder 0 must pair with each other, so count[0] must be even. An element with remainder r > 0 must pair with one of remainder k - r, so we need count[r] == count[k - r] for every r from 1 to k/2. When k is even the middle class k/2 pairs with itself; because n is even and every other class already balances, its count is automatically even by the time we reach it.

Walking through the default example arr = [1,2,3,4,5,10,6,7,8,9], k = 5: the remainders are 1, 2, 3, 4, 0, 0, 1, 2, 3, 4, giving count = [2, 2, 2, 2, 2]. count[0] = 2 is even, count[1] = count[4] = 2, and count[2] = count[3] = 2, so every class pairs up and the answer is true.

If any check fails — an odd count[0], or count[r] != count[k - r] — some element is provably left without a partner, so we can return false immediately without trying any actual pairings.

We scan the array once to build the counts and then make at most k/2 + 1 constant-time checks, so the running time is O(n + k) with O(k) extra space for the frequency table.

Time: O(n + k) Space: O(k)