Non-Divisible Subset Problem — Comprehensive Explanation

This post will help you to develop intuition for solving the Non-divisible subset problem on HackerRank which I recently came across. I found it really intriguing and requires some insight into basic properties of modular arithmetic in order to solve!

Problem :

Given a set of distinct integers S of size n, we have to print the size of a maximal subset of S where the sum of any 2 numbers in S` is not evenly divisible by k.

Constraints :- 1≤ K ≤ 100 , 1 ≤S[i] ≤ 10⁹ , 1≤ n ≤ 10⁵

Example:

Given S = [ 1, 2, 3, 4, 5, 6 ] and k = 3 .

Input: Array and the value k

Here,we can form a maximal subset of S as S`= [ 3 , 1, 4 ]. To verify we can take all possible pairs of elements from S` and check if the sum of any two elements is evenly divisible by k=3 or not.

Here 3 + 1 = 4 which is not evenly divisible by 3. Also 3 + 4 = 7 is also not evenly divisible by 3. And another possible pair we can check is 1+4 =5 which too is not evenly divisible by 3. So it satisfies the condition !

In this example, there is no way to form a subset with more than 3 elements which satisfies the condition.

Here,what we are expected to find is the size of S` and not what it contains. So in this example, our answer will be 3 as S’ contains three elements.

Note that we could have made another subset as S`= [ 3, 2, 5] which also satisfies the condition and it too has 3 elements. So we can have multiple subsets of a certain maximum size which satisfy the condition but we are concerned only with the size and not the subsets themselves.

Simple enough ! Now let’s see how we can develop the solution systematically.

Naive/Brute force approach

1. Generate all possible subsets of S.
2. Starting with the largest sized subset, check if the subset satisfies the condition. If it satisfies the condition, return its size. Else take the next largest sized subset and check if it satisfies the condition. Go on repeating this step till you have no subsets left.

This solution would be extremely slow, as it will have a time complexity of about O( 2^n * n²). The first step takes O(2^n) time for subset generation and for every generated subset, we do checking in the second step and it will take O(n²) time. Also it requires unnecessary memory for storing the subsets.

A Faster and Better Solution:

Firstly note that when you divide an integer by a number k, the remainder that you will get always ranges from 0 to k-1.

Furthermore, there is an interesting property that you can notice about a given pair of numbers, say ‘A’ and ‘B’ given a number k.

Concretely, if the sum of A and B is divisible by k i.e [ (A + B) mod k = 0] then the sum of their individual remainders is also divisible by k.

Precisely, if p = (A mod k) and q = (B mod k) and (A+B) mod k = 0, then p+q is either 0 or k.

Assume you have two nos A and B such that A+B is divisible by k. Then we can have two cases:

Case 1: When p + q is zero

p+q is zero when p=0 and q=0 , meaning that A and B themselves are perfectly divisible by k. Example if k=5 , A= 15 and B = 10 then we see that 15 and 10 themselves are perfectly divisible by 5. Hence, p=0 and q=0 and so p+q is zero. Indeed 15 + 10 = 25 is divisible by 5.

Case 2: When p + q = k

If either of A and B is not perfectly divisible by k, then the value of p+q has to be k for (A+B) to be perfectly divisible by k. E.g if k = 5 , A = 12 and B = 3, we see that p=(12 mod 5 )= 2 and q = (3 mod 5) = 3. So (p+q) = 3 + 2 = 5. This implies that A+B will be divisible by k which in this case is true as expected.

Read the two cases once again if you need to because this is the idea which leads to the solution.

Now, we want to avoid the above two cases while forming the maximal subset S` which we are trying to find.

Handling case 1: p=0 and q=0

The above analysis shows that we can have at most one number in S` from S which is perfectly divisible by k. Adding two such numbers in S’ will clearly violate the condition. In reference to the very first example, you cannot have both 3 and 6 which are evenly divisible by k=3 in S` as 3+6 = 9 is divisible by k.

Handling case 2: p + q = k

We can rewrite this equation as p = k - q. Now, what this equation indicates is that we cannot have two numbers in S` which on dividing by k give remainders p and q such that p = k - q. In reference to the very first example, you cannot have 1 and 5 in S` simultaneously as p=(1 mod 3 )= 1 and q=(5 mod 3 )=2 and therefore (p+q) = (1+2) = 3= k. And indeed, 1+5 =6 is perfectly divisible by k.

This case can be further categorized into two more sub-cases:

1. When K is odd and p = k-q:

Let’s say you found x1 numbers which on dividing by k gave remainder p and and x2 numbers which on dividing by k gave remainder q from S. And you have p = k -q. Now, in your maximal subset S` you can either include all the x1 numbers in S` or all the x2 numbers in S`. We cannot have both simultaneously. And as we want a maximal subset; for every pair of remainders p,q with p = k - q, we will include max(x1 , x2) in S`.

2. When K is even and p=k-q:

The strategy for this is almost same as that for odd case but with only one exception.

Let’s say k = 6 for example. Now the remainders we can have on dividing elements in S will be 0,1,2,3,4,5. We can see that for any two numbers, if we have p = 3 and q=3, it clearly satisfies p = 6 - q. This happens because p and q are exactly halves of k. Now, here we are dealing with the same numbers from S if we try to find x1 and x2 as mentioned previously.

So it turns out that this exception where you have p=q=k / 2 and p = k -q is similar to the case when p = 0 and q=0. You cannot have two numbers which have remainder k/2 and k/2 be in S` at the same time. So even here we can take at most one such element from S in S’.

Now, let’s see how we can apply this in an algorithmic fashion.

Step 1 : Creating a count array:

The count array will have size k with each element at an index i holding the count of numbers in S , giving remainder i when divided by k.

E.g if count[1] = 2 , then it means that there are two numbers in S such that (number mod k) = 1.

Picture illustrating how count array is calculated for the very first example.

In the above example k is odd i.e k = 3 .

In python you can do this as follows:

Seems quite easy! Right ?

Step 2: Choose appropriate numbers from count array in S`

The figure shows how you can generate solution from when k is odd .

So our final answer will be min(2 , 1) + max(2,2) = 1 + 2 = 3 . This indeed matches with the answer we found manually!

Let’s Look At One more example:

Let S = [ 12 ,6 ,1, 9, 13, 15, 10, 21, 14, 32, 5, 8, 23, 19] and k =6 (k is even).

The count array will be [2, 3, 3, 3, 1, 2].

Here’s how you can find the solution:

Figure showing solution for the example

So our final answer will be:

min(2 , 1) + max(3,2) + min(3,1) + max(3,1) = 1 + 3 + 1 + 3 = 8

Implementation:

By considering all the scenarios, here’s how we can generate a solution which works for all cases.

Time Complexity:

O(n) as the most costly operation is the loop which generates the count array.

Space Complexity:

O(k) as the size of the count array is k.

I hope that this was clear and helpful.

Thank you for reading!