Non-Divisible Subset — HackerRank Medium — Problem Solving

Non-Divisible Subset | HackerRank

This problem seems to be very hard when you have a general look at it but let's take it step by step.

For a given set of numbers S = [19,10,12,10,24,25,22] we need to find out the maximum length of the subset array in which sum of any two numbers is not evenly divisible by a given number K ( for example 4). The two different solutions that come up would be [10,12,25] and [19,22,24]. Here, 10 + 12 is not evenly divisible by 4 and neither is 10 + 25 or 12 + 25, thus a valid solution. Since both are of length 3, the answer is 3.

So how do we solve this in code?

One very important thing we need to keep in mind is that, for any two numbers if their remainders when divided by the Kth value and added together comes up to be K, they are evenly divisible by K and cannot be in the subset together. So we can take this to our advantage and count the remainders of each number and increase our counts of the remainders that come across.

Lets solve this problem for one of the test cases:

15 7

278, 576, 496, 727, 410, 124, 338, 149, 209, 702, 282, 718, 771, 575, 436

int[] remainderCounts = new int[k];
for (int i : s) {
   remainderCounts[i % k]++;
}

What this gives us is an array of remainder counts which would look like:

Which simply means, we have 2 numbers which give a remainder of 1 when the number is divided by 7, and 6 numbers which give a remainder of 2, 2 numbers give a remainder of 4 and so on.

Now moving on to the next phase is calculating the total count. Remember, if two remainders ( for example 1 ,6) add up to 7 then they cannot be in the subset together thus we take the maximum count between the two and add to our count variable,

int count = 0;
for (int j = 1; j <= (k / 2); j++) {
   if (j == k - j) {
      count++;
      continue;
   }
   count += Math.max(remainders[j], remainders[k - j]);
}

We only go up to K/2 because it ensures that we do not take duplicate value.

For example,

When j = 1, we take the max count between that of count of remainders which are 1, and count of remainders which is 7–1 = 6. This is done because we do not want to go to j = 6 and find the max between 6 , 1 because it is the same thing.

If the remainders are the same since we are only going up to k /2 , there can only be one so we simply add 1 to our count ( j == k-h)

There is one last case that we need to check, that is if our count of remainder 0 is more than 0. If so, one of those elements can be used in our result set. So we add one to our count. We cannot include more than 1 because, two of those elements is evenly divisible by K and adding two would invalidate our result set.

if (remainders[0] > 0)
   count++;

The full code would look like:

Thank you for reading! Please comment any questions you might have on this.