{x}
blog image

Check If Array Pairs Are Divisible by k

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

Solution Explanation

The problem asks whether we can partition an even-length array arr into pairs such that the sum of each pair is divisible by k. The efficient solution leverages the properties of modular arithmetic and uses a frequency counter (implemented as a hash table or array).

Core Idea:

The key insight is that if two numbers a and b sum to a multiple of k, then (a % k) + (b % k) == k or (a % k) + (b % k) == 0. This means we only need to consider the remainders when dividing by k.

Algorithm:

  1. Frequency Counting: Create a frequency counter cnt (of size k) to store the count of each remainder (0 to k-1) when elements of arr are divided by k. We use (x % k + k) % k to handle negative remainders, ensuring remainders are always non-negative.

  2. Pair Matching: For each remainder i (from 1 to k-1):

    • It must have a corresponding remainder k - i with the same frequency. If cnt[i] != cnt[k-i], we cannot form pairs, and we return false.

  3. Zero Remainder Check: The number of elements with a remainder of 0 (cnt[0]) must be even because they can only pair with other elements that also have a remainder of 0. If cnt[0] is odd, we return false.

  4. Success: If all the above conditions are met, it's possible to form pairs, and we return true.

Time and Space Complexity:

  • Time Complexity: O(n), where n is the length of the array. The frequency counting and pair matching steps both iterate through the array or the frequency counter (which is of size k, and k is typically much smaller than n).

  • Space Complexity: O(k), where k is the divisor. The space is dominated by the frequency counter cnt, which has a size proportional to k.

Code Explanation (Python):

from collections import Counter
 
class Solution:
    def canArrange(self, arr: List[int], k: int) -> bool:
        cnt = Counter(x % k for x in arr) #Efficient frequency counting using Counter
        return cnt[0] % 2 == 0 and all(cnt[i] == cnt[k - i] for i in range(1, k)) #Checks for pair and zero conditions

The Python code directly uses the Counter object from the collections module for efficient frequency counting. The all() function concisely checks the pairing condition. The other language solutions achieve the same logic using arrays or maps as frequency counters. The handling of negative remainders is crucial for correctness; (x % k + k) % k ensures positive remainders.