DEV Community

ways!
ways!

Posted on

1497. Check If Array Pairs Are Divisible by k

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]++;
}
Enter fullscreen mode Exit fullscreen mode
  • 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;
    }
}
Enter fullscreen mode Exit fullscreen mode
  • 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.

Top comments (0)