Domain 2MediumMEDIUM

Check If Array Pairs Are Divisible by k

LeetCode problem 1497: Check If Array Pairs Are Divisible by k (medium).

Domain: medium•Updated: 2026-09-17
#Array#Math#Greedy

Problem Breakdown

We are given an array arr of even length nn and a divisor integer kk. The goal is to determine if we can partition all elements into exactly n/2n/2 pairs such that for every pair (a,b)(a, b), the sum (a+b)(a + b) is divisible by kk.

Inputs:

  • arr: List of integers (even length).
  • k: Positive integer divisor.

Outputs:

  • Boolean: True if a valid pairing exists, False otherwise.

Implicit Constraints & Edge Cases:

  1. 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 k≥1k \ge 1, x % k will always be in range [0, k-1]. This simplifies pairing logic significantly compared to other languages.
  2. Zero Remainder: Elements divisible by kk (remainder 0) must pair with each other. Thus, the count of elements where arr[i] % k == 0 must be even.
  3. Half-Remainder Case: If kk is even, there exists a remainder equal to exactly half (k/2k/2). Elements with this remainder sum up to kk, which is divisible by kk. These elements must also pair among themselves (e.g., (1+4)(1+4) where k=5k=5? No wait. Remainder 0 pairs with 0. Remainder rr pairs with k−rk-r. If 2r=k2r = k, then remainder rr pairs with itself). Thus, the count of elements with remainder k/2 must be even if such a case exists (i.e., when k%2==0k \% 2 == 0 and we consider remainder k/2k/2).
  4. Symmetry: For any other remainder rr, there must exist an equal number of elements with remainder (k−r)(k - r).

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 (O(N!)O(N!)), which will Time Out (TLE). Even trying every subset of size 2 is O(N3)O(N^3).

Key Insight: We can leverage modular arithmetic properties: (a+b)≡0(modk)(a + b) \equiv 0 \pmod k implies that the sum of their remainders modulo kk must be divisible by kk. Specifically, if we define remainder r=x%kr = x \% k, then for a pair to work, either both have remainder 0 (sum is multiple of kk), or they have complementary remainders such that (a%k+b%k)==k(a\%k + b\%k) == k.

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 rr with a corresponding k−rk-r, and ensure 0s/half remainders are even in count, then it is possible.

Approach

  1. Normalize Remainders: Iterate through the array arr and compute (x % k) for each element. Store frequencies of these remainders using a hash map (or Counter).

  2. Check Zero Case: Elements with remainder 0 must pair up among themselves. If their count is odd, return False.

  3. Iterate Remainder Pairs: Iterate through possible non-zero remainders rr from 11 to (k//2)(k // 2). Note that we only need to check the first half of potential remainders because checking rr implicitly checks its complement k−rk-r.

    • If counts[r] is not equal to counts[k - r], return False. This ensures every element with remainder rr has a matching partner for sum divisibility.
  4. Handle Half-Remainder: If kk is even, the specific case where 2×(k/2)=k2 \times (k/2) = k exists. Elements with remainder exactly k/2k/2 must pair up among themselves. Check if their count is even. Note that this falls naturally into the loop logic (r==k−rr == k-r), 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 k/2k/2 isn’t treated like a standard pair).

    • Actually, simpler logic: Iterate unique keys found. But the range loop 1..k//2 is 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, K≤105K \le 10^5. It’s fine.
    • Wait, strictly speaking: If I iterate r from 1 to (k // 2), and check if counts[r] == counts[k-r]. This covers all pairs including the middle one (k/2k/2). For r=k/2r = k/2, it checks counts[k/2] == counts[k - k/2] which is counts[k/2] == counts[k/2], always true. So we need to explicitly check if count of k/2k/2 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 == 0 when r == k - r. Or simply check if count of k/2k/2 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 r=k/2r = k/2, then counts[r] == counts[k-r] is trivially true (x==xx==x). We need to ensure count is even for that specific case. So we must handle remainder 0 and remainder k/2k/2 (if exists) as special cases requiring even counts, while other remainders require matching pairs.

    Refined Algorithm:

    • Compute counts of (x % k) for all x in arr.
    • Check if counts[0] is odd -> return False.
    • If kk is even: check if counts[k // 2] is odd -> return False.
    • Iterate r from 1 to (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 rr and k−rk-r. 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 1 to (k // 2). Check equality of counts for rr and k−rk-r. If mismatch -> False. Handle special cases (00, k/2k/2).

Complexity Analysis

  • Time Complexity: O(N+K)O(N + K)
    • We iterate through the array arr once to build the frequency map: O(N)O(N).
    • We then check remainders up to K/2K/2: O(K)O(K).
    • Given constraints (N,K≤105N, K \le 10^5), this is well within time limits. Note that if we only iterate over unique keys present in the map (bounded by min⁡(N,K)\min(N, K)), it could be slightly faster on average but worst-case remains O(K)O(K).
  • Space Complexity: O(min⁡(N,K))O(\min(N, K)) or O(K)O(K) depending on implementation. We store counts for remainders up to K−1K-1, 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 % 5 becomes 4. This correctly identifies that a number with remainder 4 needs to pair with one having remainder 1 (since 4+1=54+1=5).
  • Zero Remainder: The code explicitly checks if elements divisible by k (counts[0]) appear an even number of times. If odd, it returns False.
  • Half-Remainder (k/2k/2): When kk 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 False in 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 (0==00 == 0), unless one side exists without the other, which triggers a