Intuition¶

The problem asks to check whether the array can be arranged into pairs such that the sum of each pair is divisible by a given integer k. The first thought is that for every element in the array, the sum of its remainder when divided by k with the remainder of another element should be equal to k. Special attention is needed for elements perfectly divisible by k, and handling of negative numbers is also required.

Approach¶

Create an array to keep track of the frequency of remainders when elements are divided by k.
Traverse the array and calculate the remainder for each element. Adjust for negative numbers so that all remainders are positive.
After building the frequency array, check if the remainder counts satisfy the conditions:
The count of elements with remainder i should match the count of elements with remainder k - i for all remainders.
For elements perfectly divisible by k (i.e., remainder 0), the count must be even to allow pairing.
If all conditions are met, return true. Otherwise, return false.

Complexity¶

Time complexity:
$O(n)$ where n is the number of elements in the array since we only make two passes over the array.
Space complexity:
$O(k)$ for the remainder counts array, where k is the given divisor.

Code¶

class Solution {
    public boolean canArrange(int[] arr, int k) {
        int[] remainderCounts = new int[k];

        for (int num : arr) {
            int remainder = ((num % k) + k) % k;
            remainderCounts[remainder]++;
        }

        for (int i = 1; i < k; i++) {
            if (remainderCounts[i] != remainderCounts[k - i]) {
                return false;
            }
        }

        return remainderCounts[0] % 2 == 0;
    }
}