Problem Breakdown
We are given an array arr of even length and a divisor integer . The goal is to determine if we can partition all elements into exactly pairs such that for every pair , the sum is divisible by .
Inputs:
arr: List of integers (even length).k: Positive integer divisor.
Outputs:
- Boolean:
Trueif a valid pairing exists,Falseotherwise.
Implicit Constraints & Edge Cases:
- Negative Numbers: The problem allows negative values in the array. In many languages (like C++/Java),
%can return negative results for negative operands, which breaks simple modulo logic. However, Python’s%operator returns a result with the same sign as the divisor (k). Since ,x % kwill always be in range[0, k-1]. This simplifies pairing logic significantly compared to other languages. - Zero Remainder: Elements divisible by (remainder 0) must pair with each other. Thus, the count of elements where
arr[i] % k == 0must be even. - Half-Remainder Case: If is even, there exists a remainder equal to exactly half (). Elements with this remainder sum up to , which is divisible by . These elements must also pair among themselves (e.g., where ? No wait. Remainder 0 pairs with 0. Remainder pairs with . If , then remainder pairs with itself). Thus, the count of elements with remainder
k/2must be even if such a case exists (i.e., when and we consider remainder ). - Symmetry: For any other remainder , there must exist an equal number of elements with remainder .
Intuition
Brute Force Approach: The naive approach would be to try all possible permutations or combinations to form pairs and check divisibility for each configuration. This is factorial time complexity (), which will Time Out (TLE). Even trying every subset of size 2 is .
Key Insight: We can leverage modular arithmetic properties: implies that the sum of their remainders modulo must be divisible by . Specifically, if we define remainder , then for a pair to work, either both have remainder 0 (sum is multiple of ), or they have complementary remainders such that .
This transforms the problem from “pairing numbers” to “matching buckets”. We just need to count how many elements fall into each remainder bucket. If we can match every non-zero, non-half-remainder with a corresponding , and ensure 0s/half remainders are even in count, then it is possible.
Approach
-
Normalize Remainders: Iterate through the array
arrand compute(x % k)for each element. Store frequencies of these remainders using a hash map (or Counter). -
Check Zero Case: Elements with remainder 0 must pair up among themselves. If their count is odd, return
False. -
Iterate Remainder Pairs: Iterate through possible non-zero remainders from to . Note that we only need to check the first half of potential remainders because checking implicitly checks its complement .
- If
counts[r]is not equal tocounts[k - r], returnFalse. This ensures every element with remainder has a matching partner for sum divisibility.
- If
-
Handle Half-Remainder: If is even, the specific case where exists. Elements with remainder exactly must pair up among themselves. Check if their count is even. Note that this falls naturally into the loop logic (), but we need to ensure
counts[r]is divisible by 2 in that specific iteration or handle it separately before iterating to avoid index confusion (though checking equality handles odd counts correctly as long as isn’t treated like a standard pair).- Actually, simpler logic: Iterate unique keys found. But the range loop
1..k//2is robust against missing complements in sparse arrays if we assume empty buckets have count 0. However, iterating up to K might be slower than N? No, . It’s fine. - Wait, strictly speaking: If I iterate
rfrom1to(k // 2), and check ifcounts[r] == counts[k-r]. This covers all pairs including the middle one (). For , it checkscounts[k/2] == counts[k - k/2]which iscounts[k/2] == counts[k/2], always true. So we need to explicitly check if count of is even? - Correction: If I iterate range, checking equality doesn’t verify parity for the middle element itself (since it compares with self). We must ensure
counts[r] % 2 == 0whenr == k - r. Or simply check if count of is even separately. - Actually, a cleaner way: Iterate through unique keys in Counter? No, range loop ensures we cover all buckets required for symmetry regardless of input sparsity (assuming empty buckets are 0). But wait, iterating up to K might be wasteful if N << K and remainders don’t exist there.
- Better Logic: Use the
Counter. Iterate through unique keys in Counter? No, because we need to ensure complements match even if complement isn’t a key (count is 0). So iterate range(1, k//2 + 1) checking against map with default value of 0. - Wait, iterating up to K/2 handles the middle element check implicitly? If , then
counts[r] == counts[k-r]is trivially true (). We need to ensure count is even for that specific case. So we must handle remainder 0 and remainder (if exists) as special cases requiring even counts, while other remainders require matching pairs.
Refined Algorithm:
- Compute
countsof(x % k)for all x in arr. - Check if
counts[0]is odd -> return False. - If is even: check if
counts[k // 2]is odd -> return False. - Iterate
rfrom1to(k - 1). Wait, iterating all keys? No, iterate unique remainders present in input or range up to k/2. Let’s stick to the most robust: Check symmetry for and . Since we need exact pairing counts, if any remainder exists that doesn’t have a matching complement count (or is 0/half-remainder with odd count), fail. - Actually, simplest code structure: Iterate
1to(k // 2). Check equality of counts for and . If mismatch -> False. Handle special cases (, ).
- Actually, simpler logic: Iterate unique keys found. But the range loop
Complexity Analysis
- Time Complexity:
- We iterate through the array
arronce to build the frequency map: . - We then check remainders up to : .
- Given constraints (), this is well within time limits. Note that if we only iterate over unique keys present in the map (bounded by ), it could be slightly faster on average but worst-case remains .
- We iterate through the array
- Space Complexity: or depending on implementation. We store counts for remainders up to , so space is proportional to the size of
k.
Solution
from collections import Counter
def check_pairs(arr: list[int], k: int) -> bool:
# Step 1: Count frequencies of each remainder modulo k.
# Python's % operator handles negative numbers correctly for this logic
# (e.g., -5 % 3 = 1), ensuring remainders are in range [0, k-1].
counts = Counter(x % k for x in arr)
# Step 2: Handle remainder 0. Elements divisible by k must pair with each other.
if counts[0] % 2 != 0:
return False
# Step 3: Iterate through the first half of remainders to check symmetry.
# We only need to check r from 1 up to (k // 2).
# If k is even, we must handle remainder k/2 separately because it pairs with itself.
for i in range(1, (k // 2) + 1):
if counts[i] != counts[k - i]:
return False
# Special check: If k is even, the middle element (k//2) must also have an even count
# because it pairs with itself. The loop above checks equality but not parity for self-pairing case.
if k % 2 == 0 and counts[k // 2] % 2 != 0:
return False
return True
# Example usage / Test cases (commented out to keep solution clean)
# print(check_pairs([1,2,3,4,5,10,6,7,8,9], 5)) # True
Edge Cases Handled
- Negative Numbers: Python’s
%operator normalizes negative inputs into the positive range[0, k-1], so-1 % 5becomes4. This correctly identifies that a number with remainder 4 needs to pair with one having remainder 1 (since ). - Zero Remainder: The code explicitly checks if elements divisible by
k(counts[0]) appear an even number of times. If odd, it returnsFalse. - Half-Remainder (): When is even (e.g., 10), a remainder of 5 must pair with another 5 to sum to 10. The code checks if the count for this specific bucket is odd and returns
Falsein that case. - Sparse Remainders: If many remainders are not present in the input, their counts default to 0 (via Counter). Comparing a missing remainder with its complement works correctly (), unless one side exists without the other, which triggers a