# Check If Array Pairs Are Divisible by k
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/check-if-array-pairs-are-divisible-by-k)
Canonical: https://scaleengineer.com/dsa/problems/check-if-array-pairs-are-divisible-by-k
**Patterns:** [Counting](https://scaleengineer.com/dsa/patterns/counting)
**Data structures:** Array, Hash Table
**Companies:** [Visa](https://scaleengineer.com/companies/visa), [DevRev](https://scaleengineer.com/companies/devrev)
---
## Problem
Given an array of integers `arr` of even length `n` and an integer `k`.

We want to divide the array into exactly `n / 2` pairs such that the sum of each pair is divisible by `k`.

Return `true` _If you can find a way to do that or_ `false` _otherwise_.

**Example 1:**

**Input:** arr = [1,2,3,4,5,10,6,7,8,9], k = 5
**Output:** true
**Explanation:** Pairs are (1,9),(2,8),(3,7),(4,6) and (5,10).

**Example 2:**

**Input:** arr = [1,2,3,4,5,6], k = 7
**Output:** true
**Explanation:** Pairs are (1,6),(2,5) and(3,4).

**Example 3:**

**Input:** arr = [1,2,3,4,5,6], k = 10
**Output:** false
**Explanation:** You can try all possible pairs to see that there is no way to divide arr into 3 pairs each with sum divisible by 10.

**Constraints:**

* `arr.length == n`
* `1 <= n <= 105`
* `n` is even.
* `-109 <= arr[i] <= 109`
* `1 <= k <= 105`

# Approaches
## Brute-force with Backtracking
This approach attempts to solve the problem by exploring every possible way to form pairs from the array elements. It uses a classic backtracking algorithm to try all combinations. If it finds any single valid partition of the array into `n/2` pairs where each pair's sum is divisible by `k`, it concludes that it's possible and returns `true`.
**Time:** O((n-1)!!) which is approximately O((n/2)!). This is factorial-level complexity, arising from the number of ways to partition `n` items into `n/2` pairs. It is computationally infeasible for the given constraints. · **Space:** O(n) for the recursion stack depth and the `used` boolean array.
**Pros:** Conceptually straightforward as it directly models the problem of trying all pairings.
**Cons:** Extremely inefficient and slow.; Guaranteed to cause a 'Time Limit Exceeded' (TLE) error for the constraints specified in the problem (n up to 10^5).; Not a practical solution for anything beyond very small input sizes.
### Explanation
The core idea is to build the pairs one by one. We use a boolean array `used` to keep track of elements that have already been included in a pair.

A recursive function, say `findPairs`, attempts to form the remaining pairs. The function finds the first available element `arr[i]` and tries to pair it with every other available element `arr[j]`. If `(arr[i] + arr[j]) % k == 0`, we tentatively form this pair, mark both elements as used, and then recursively call the function to form the next pair from the remaining elements.

If a recursive call eventually leads to a state where all `n/2` pairs are formed, we have found a solution. If a path leads to a dead end (e.g., an element cannot be paired with any remaining element), we "backtrack" by undoing the last pair formation and trying a different option.

```java
class Solution {
    public boolean canArrange(int[] arr, int k) {
        boolean[] used = new boolean[arr.length];
        return findPairs(arr, k, used, 0);
    }

    private boolean findPairs(int[] arr, int k, boolean[] used, int pairsFormed) {
        if (pairsFormed == arr.length / 2) {
            return true;
        }

        // Find the first unused element's index
        int i = -1;
        for (int idx = 0; idx < arr.length; idx++) {
            if (!used[idx]) {
                i = idx;
                break;
            }
        }

        if (i == -1) {
            // Should not be reached if pairsFormed < arr.length / 2
            return true; 
        }

        used[i] = true;

        // Try to find a pair for arr[i]
        for (int j = i + 1; j < arr.length; j++) {
            if (!used[j]) {
                // Note: The problem statement guarantees arr[i] can be negative.
                // A simple (a + b) % k == 0 works for both positive and negative numbers in Java
                // as long as we are just checking for a zero result.
                if ((arr[i] + arr[j]) % k == 0) {
                    used[j] = true;
                    if (findPairs(arr, k, used, pairsFormed + 1)) {
                        return true;
                    }
                    used[j] = false; // Backtrack
                }
            }
        }

        used[i] = false; // Backtrack
        return false;
    }
}
```
### Algorithm
*   Initialize a boolean array `used` of size `n` to `false` to track which elements have been paired.
*   Define a recursive helper function, for example, `findPairs(arr, k, used, pairsFormed)`.
*   **Base Case:** If `pairsFormed` equals `n / 2`, it means all elements have been successfully paired. Return `true`.
*   **Recursive Step:**
    *   Find the first element `arr[i]` that has not been used yet (`used[i]` is `false`).
    *   Mark `arr[i]` as used (`used[i] = true`).
    *   Iterate through the subsequent elements `arr[j]` (where `j > i`).
    *   If `arr[j]` is not used and `(arr[i] + arr[j]) % k == 0`, we have found a potential pair.
    *   Mark `arr[j]` as used and make a recursive call `findPairs(arr, k, used, pairsFormed + 1)`.
    *   If the recursive call returns `true`, it means a full valid partition was found, so we return `true` up the call stack.
    *   If the call returns `false`, we must backtrack. Unmark `arr[j]` as used (`used[j] = false`) and continue searching for another partner for `arr[i]`.
*   If the loop finishes without finding a suitable partner for `arr[i]`, it's impossible to form a valid partition from this state. We backtrack by unmarking `arr[i]` and return `false`.

## Optimal Approach using Frequency of Remainders
A much more efficient and optimal approach leverages modular arithmetic. The key insight is that for a pair `(a, b)` to have a sum divisible by `k`, their remainders must complement each other. That is, `(a % k + b % k) % k == 0`. This implies that for an element with remainder `r`, its partner must have a remainder of `k - r` (or `0` if `r` is `0`). Instead of trying to pair actual numbers, we can just count the frequencies of their remainders and check if these counts allow for a valid pairing.
**Time:** O(n + k). We iterate through the input array of size `n` once to build the frequency map, and then we iterate through the frequency array of size `k` (or `k/2`) once to check the conditions. · **Space:** O(k), as we need an auxiliary array of size `k` to store the frequencies of the remainders.
**Pros:** Highly efficient with linear time complexity.; Optimal solution for the given constraints.; Handles all edge cases, including negative numbers, correctly and elegantly.
**Cons:** Requires extra space proportional to `k`, which could be large if `k` is very large (though it's fine for the given constraints).
### Explanation
This method transforms the problem from pairing numbers to pairing remainders. We don't care about the numbers themselves, only their remainders when divided by `k`.

The algorithm proceeds in two main phases:
1.  **Counting Remainders:** We iterate through the entire input array `arr` once. For each number, we compute its remainder modulo `k`. A crucial detail is handling potentially negative numbers in `arr`. The standard `%` operator in Java can yield negative results (e.g., `-1 % 5` is `-1`). To map all remainders to the non-negative range `[0, k-1]`, we use the expression `((num % k) + k) % k`. We use an array of size `k` to store the frequency of each of these non-negative remainders.

2.  **Verifying Frequencies:** After counting, we check if the frequencies allow for perfect pairing.
    *   **Remainder 0:** An element `x` with `x % k == 0` needs a partner `y` with `y % k == 0`. This means all elements divisible by `k` must be paired amongst themselves. Therefore, the total count of such elements (`remainderCounts[0]`) must be even.
    *   **Complementary Remainders:** An element `x` with remainder `r` (where `r != 0`) needs a partner `y` with remainder `k - r`. This means the number of elements with remainder `r` must exactly match the number of elements with remainder `k - r`.
    *   **Special Case `r = k/2`:** If `k` is an even number, a special case arises for the remainder `r = k / 2`. Here, `k - r = r`, so an element with this remainder must be paired with another element that also has the same remainder. Consequently, the count of elements with remainder `k/2` must be even.

If all these conditions hold, we can form the pairs, so we return `true`. Otherwise, it's impossible, and we return `false`.

```java
class Solution {
    public boolean canArrange(int[] arr, int k) {
        int[] remainderCounts = new int[k];
        for (int num : arr) {
            int rem = ((num % k) + k) % k;
            remainderCounts[rem]++;
        }

        // Condition 1: Count of numbers with remainder 0 must be even.
        if (remainderCounts[0] % 2 != 0) {
            return false;
        }

        // Condition 2: For r from 1 to k/2, check complementary pairs.
        for (int r = 1; r <= k / 2; r++) {
            // If r is its own complement (only when k is even and r = k/2)
            if (r * 2 == k) {
                if (remainderCounts[r] % 2 != 0) {
                    return false;
                }
            } else {
                // For all other r, count(r) must equal count(k-r).
                if (remainderCounts[r] != remainderCounts[k - r]) {
                    return false;
                }
            }
        }

        return true;
    }
}
```
### Algorithm
*   Create an integer array `remainderCounts` of size `k`, initialized to all zeros. This array will store the frequency of each possible remainder.
*   Iterate through each number `num` in the input array `arr`.
*   For each `num`, calculate its remainder modulo `k`. To handle negative numbers correctly and ensure the remainder is in the range `[0, k-1]`, use the formula `rem = ((num % k) + k) % k`.
*   Increment the count for this remainder: `remainderCounts[rem]++`.
*   After populating the frequency array, check the pairing conditions:
    *   Check `remainderCounts[0]`. Since elements with a remainder of 0 can only be paired with other elements with a remainder of 0, their total count must be even. If `remainderCounts[0] % 2 != 0`, return `false`.
    *   Iterate from `r = 1` up to `k / 2`.
    *   For each `r`, if `r * 2 == k` (which only happens if `k` is even and `r = k/2`), these elements must pair with each other. Thus, `remainderCounts[r]` must be even. If not, return `false`.
    *   Otherwise (if `r != k-r`), an element with remainder `r` must pair with an element with remainder `k-r`. Therefore, their counts must be equal. If `remainderCounts[r] != remainderCounts[k - r]`, return `false`.
*   If all conditions are met after checking all remainders, it means a valid pairing is possible. Return `true`.

# Solutions
### Java

```java
class Solution {
public
  boolean canArrange(int[] arr, int k) {
    int[] cnt = new int[k];
    for (int x : arr) {
      ++cnt[(x % k + k) % k];
    }
    for (int i = 1; i < k; ++i) {
      if (cnt[i] != cnt[k - i]) {
        return false;
      }
    }
    return cnt[0] % 2 == 0;
  }
}

```

### JavaScript

```javascript
function canArrange ( arr , k ) { const cnt = Array ( k ). fill ( 0 ); for ( const x of arr ) { cnt [(( x % k ) + k ) % k ] ++ ; } for ( let i = 1 ; i < k ; i ++ ) { if ( cnt [ i ] !== cnt [ k - i ]) return false ; } return cnt [ 0 ] % 2 === 0 ; }
```

### CPP

```cpp
class Solution {
public:
  bool canArrange(vector<int> &arr, int k) {
    vector<int> cnt(k);
    for (int &x : arr) {
      ++cnt[((x % k) + k) % k];
    }
    for (int i = 1; i < k; ++i) {
      if (cnt[i] != cnt[k - i]) {
        return false;
      }
    }
    return cnt[0] % 2 == 0;
  }
};

```

### Python

```python
class Solution:
    def canArrange(self, arr: List[int], k: int) -> bool: cnt = Counter(x % k for x in arr) return cnt[0] % 2 == 0 and all(cnt[i] == cnt[k - i] for i in range(1, k))

```