cyberangles blog

Subset with no pair sum divisible by K

In the world of algorithms and combinatorial problems, finding a subset of a given set of integers such that the sum of any two elements in the subset is not divisible by a given integer (K) is an interesting and challenging task. This problem has applications in various areas like resource allocation (where we might want to group tasks in a way that certain combined "loads" don't meet a particular divisibility condition) and in designing hash functions with specific collision - avoidance properties. In this blog, we will explore different approaches to solve this problem.

2026-07

Table of Content#

  1. Problem Statement
  2. Brute - Force Approach (Naive Method)
  3. Optimal Approach using Frequency Arrays
  4. Example Usage
  5. Best Practices
  6. Common Pitfalls
  7. References

1. Problem Statement#

Given an array (A) of (n) integers and an integer (K), we need to find the size of the largest subset (S) of (A) such that for any two elements (a) and (b) in (S), ((a + b)\bmod K\neq0).

2. Brute - Force Approach (Naive Method)#

2.1 Idea#

The brute - force approach involves generating all possible subsets of the given array and then checking for each subset whether the sum of any two elements in the subset is not divisible by (K).

2.2 Algorithm#

  • Generate all subsets of the array (A) using techniques like bit - masking (for small (n), say (n\leq20)).
  • For each subset (S):
    • Iterate over all pairs ((a,b)) in (S).
    • Check if ((a + b)\bmod K = 0). If such a pair exists, discard the subset.
    • If no such pair exists, record the size of the subset.
  • Return the maximum size of the valid subsets.

2.3 Complexity#

  • Time Complexity: (O(2^n\times n^2)). Since there are (2^n) subsets (in the worst - case for bit - masking) and for each subset, we need to check (O(n^2)) pairs. This approach is only feasible for very small values of (n) (e.g., (n < 15)).
  • Space Complexity: (O(1)) (excluding the space for storing subsets, which is (O(2^n)) in the worst - case).

3. Optimal Approach using Frequency Arrays#

3.1 Idea#

We can use the property of modular arithmetic. Let's first calculate the remainder of each element in the array when divided by (K). We will use a frequency array (freq) where (freq[i]) represents the number of elements in the array with a remainder (i) when divided by (K).

  • For (i = 0): We can take at most one element with remainder (0) (because if we take two elements (a) and (b) with (a\bmod K=0) and (b\bmod K = 0), then ((a + b)\bmod K=0)).
  • For (i\in(1, K - 1)): If (i\neq K - i), we can take the maximum of (freq[i]) and (freq[K - i]). If (i = K - i) (i.e., (K) is even and (i=\frac{K}{2})), we can take at most one element.

3.2 Algorithm#

  1. Initialize a frequency array (freq) of size (K) with all elements set to (0).
  2. Iterate over the array (A):
    • For each element (a) in (A), calculate (r=a\bmod K).
    • Increment (freq[r]) by (1).
  3. Initialize the result (res = 0).
  4. For (i = 1) to (\lfloor\frac{K}{2}\rfloor):
    • If (i\neq K - i):
      • (res+=\max(freq[i], freq[K - i]))
    • Else (when (K) is even and (i=\frac{K}{2})):
      • (res += 1) (if (freq[i]>0))
  5. If (freq[0]>0):
    • (res += 1)
  6. Return (res)

3.3 Complexity#

  • Time Complexity: (O(n)) (for iterating over the array to calculate remainders and then (O(K)) for processing the frequency array). Since (K) is usually a small constant (compared to (n)), the overall time complexity is (O(n)).
  • Space Complexity: (O(K)) (for the frequency array).

4. Example Usage#

4.1 Input#

Let (A={3,1,7,5}) and (K = 4)

  • Calculate remainders: (3\bmod4 = 3), (1\bmod4=1), (7\bmod4 = 3), (5\bmod4 = 1)
  • Frequency array (freq=[0, 2, 0, 2]) (since (freq[0]=0), (freq[1]=2), (freq[2]=0), (freq[3]=2))

4.2 Processing#

  • For (i = 1): (K - i=3). (\max(freq[1], freq[3])=\max(2,2) = 2)
  • (freq[0]=0), so we don't add anything for the remainder (0)
  • Result (res = 2)

The valid subset could be ({1,7}) (since ((1 + 7)\bmod4=(8)\bmod4 = 0) is wrong. Wait, let's correct. The valid subset is ({1,5}) (because ((1 + 5)\bmod4=6\bmod4 = 2\neq0))

5. Best Practices#

  • Pre - processing: Always calculate the remainders of the elements with respect to (K) first. This simplifies the problem and allows us to use the frequency array approach.
  • Edge Cases:
    • When (K = 1): In this case, any non - empty subset will have pairs whose sum is divisible by (K) (since (a + b\bmod1=0) for all integers (a) and (b)). So the answer is (1) (if the array is non - empty) or (0) (if the array is empty).
    • When (K = 2): We can take all elements with remainder (1) and at most one element with remainder (0).

6. Common Pitfalls#

  • Forgetting about the remainder (0) case: Remember that we can take at most one element with remainder (0).
  • Incorrect handling of even (K): When (K) is even, the middle remainder ((\frac{K}{2})) needs special handling (we can take at most one element with that remainder).

7. References#