Question Link : 1497. Check If Array Pairs Are Divisible by k

[Problem Statement]

Given an array of integers arr of even length n and an integer k, we need to determine if it's possible to divide the array into exactly n/2 pairs such that the sum of each pair is divisible by k. The function should return true if such a division is possible, and false otherwise.

Key Insight

The crucial insight that makes this algorithm efficient is based on the properties of modular arithmetic:

1. If (a + b) % k == 0, then (a % k + b % k) % k == 0.
2. This means that for two numbers to sum to a multiple of k, their remainders when divided by k must sum to k (or 0, which is the same in modular arithmetic).

Algorithm Steps

1. Initialize Remainder Count:

   • Create an array remainders of length k, initialized with zeros.
   • This array will count how many numbers in arr have each possible remainder when divided by k.

2. Count Remainders:

   • Iterate through each number num in the input array arr.
   • Calculate its remainder when divided by k using ((num % k) + k) % k.
   • Increment the count for this remainder in the remainders array.

3. Check Pairing Possibility:

   • Iterate through the remainders from 0 to k/2: a. For remainder 0 and k/2 (if k is even):
     • Check if the count is even. If not, return false. b. For all other remainders i:
     • Check if the count of remainder i equals the count of remainder k-i.
     • If not, return false.

4. Return Result:

   • If all checks pass, return true.

Detailed Breakdown

Counting Remainders

for (let num of arr) {
    remainders[((num % k) + k) % k]++;
}

• We use ((num % k) + k) % k instead of just num % k to handle negative numbers correctly.
• This ensures all remainders are in the range [0, k-1].

Checking Pairing Possibility

for (let i = 0; i <= k / 2; i++) {
    if (i === 0 || (k % 2 === 0 && i === k / 2)) {
        if (remainders[i] % 2 !== 0) return false;
    } else {
        if (remainders[i] !== remainders[k - i]) return false;
    }
}

• We only need to check up to k/2 because remainders pair symmetrically.
• For remainder 0 and k/2 (when k is even), we need an even count because these can only pair with themselves.
• For all other remainders i, we need the count of i to equal the count of k-i, as these will pair with each other.

Time and Space Complexity

• Time Complexity: O(n + k), where n is the length of arr.
  • We iterate through arr once to count remainders: O(n)
  • We then iterate through half of k to check pairing: O(k/2)
• Space Complexity: O(k) for the remainders array.

Why This Works

• By counting remainders, we reduce the problem from checking every possible pair (which would be O(n^2)) to checking if remainders can be paired (which is O(n + k)).
• The pairing check ensures that for every number with remainder i, there's a corresponding number with remainder k-i to pair with it, such that their sum is divisible by k.

Edge Cases and Considerations

• The algorithm correctly handles negative numbers.
• It works for any positive integer k.
• It implicitly handles the case where some numbers in arr are already divisible by k (remainder 0).

This algorithm efficiently solves the problem by leveraging properties of modular arithmetic, avoiding the need to actually form the pairs or check every possible pairing.