Check If Array Pairs Are Divisible by k

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.

• 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.

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.

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;
    }
}