Max Non-Divisible Subset — What is There Under the Hood?
This article is intended as an explanation of the math required to solve the following challenge:
Problem
The goal is to find, given a set of numbers, the size of the biggest possible subset, whose values, when summed in all possible pairs, will not be evenly divisible by a given integer K.
For example:
S = {1 , 7, 2, 4}, K = 3
The biggest subset that complies with the condition is {1,7,4} because all sums of possible combinations results in values not evenly divisible by 3:
(1+7)/3 = 2.66
(1+4)/3 = 1.66
(7+4)/3 = 3.66
2 cannot be in this set because, for instance, 7+2 = 9, and 9/3 is 3, which is an even number.
Expressing this in mathematical notation, we have:
And the goal is:
While there are very good articles around that explain how to solve this problem, I haven’t found any that takes the trouble to explain the math behind it, and I think this is the kind of programming challenge which biggest benefit is understanding said math so that you can apply it later on.
However, if you want a shorter article that explains the practical part of this problem, I think this one is great. I used it myself to understand what math properties should be applied:
How to approach this problem
I will go very slowly over the steps. Let’s start with Euclid’s Division Lemma:
All fractional numbers can be expressed in this way. Remember that if r is 0, a % q = 0, or, in other words, r can be divided evenly by q.
In this case, we have pairs of numbers in the set S, that when summed, they must not be divisible by K, to conform the set T.
Let's take two elements and sum them, expressing the result with Euclid’s division lemma:
We know that K is an integer as this is specified in the problem. Then, is the rest of the right side of this expression, an integer?
Generally speaking then, s1+s2 is not evenly divisible by K, due to the fractional elements p/K and q/K. Remember than p and q are the remainder of the divisions of s1 by K and s2 by K, so they are smaller than K.
However, we can find two exceptions in which the term in the parentheses will be a natural number. First, those two fractional terms could be zero. The only way in which that can happen is if p and q are both 0.
In this case, s1+s2 divided by K would result in (m+n), and as m and n are natural numbers, s1+s2 can be divided evenly by K.
The other possibility would be that p/K + q/K sum to an integer. As we are dealing entirely with non negative numbers, it can only happen that the result is positive. Also, as p and q are both smaller than K, so each fraction is less than 1 and then they could only sum up to one.
To have p/K + q/K = 1, we need p+q = K. Applying this condition to Euclid’s division lemma, we get:
So we now know which numbers we can put in our set: all those whose remainders when divided by K cannot sum up to K (case p+q = K) or are not themselves evenly divided by K (p =0 and q = 0).
We could then, for instance, take all numbers out of our set S that have remainder 3 and put them safely in the set T, because they cannot among themselves break the rule.
Converting this into an algorithm
At this point, we have an understanding of what we need to avoid, p+q = K and p+q = 0. One approach to solving this problem is to iterate over the set S, applying the operation S%K, and making a count array with this values. All elements that have modulo 0 will count up the array[0], elements with modulo 1 will count up the array[1] and so on.
Then, as the array is of size K, we know that the extreme end element and the second element will sum K, the third element element and the penultimate element will sum K, and so on:
It does not matter which elements generate these moduli, as we have a general rule to decide if said elements can be added to T. For instance, we know that we can take all the elements that generated the count 7 at the position 1 and all the elements that generated the count 9 at position 2, we could safely put both in T, as 1+2 is not 6.
We need to focus in the things that we cannot add to T. The original member of S that generated each value of the count cannot be added multiple times as T is a set and each member has to be unique. We traverse the array from the position 1 to position K and we approach from both ends towards the center, as shown with the curly brackets in the previous image.
We cannot take both sets of elements because in those scenarios, p+q = K, so we take the biggest of each.
Now, what to do with the count at position 0? This element falls under the case p+q = 0, and all such elements when summed, will be divisible by K. So, we can only use 1 of the elements of this subset.
There is another irksome scenario, where in our image, p and q are equal. Be mindful that this can only happen if K is even. Graphically in our count array, this happens at the “center” (if we don’t consider the position 0).
What happens here?
These numbers break the rule p + q = K amongst themselves, because p = q, p+p = K:
In this case then, only one element can be taken from the subset (very similar to p+q = 0). Here is the code than handles both scenarios:
Finally, we sum the main scenario and the two special scenarios:
I hope you have found it useful and/or instructive. Let me know if there is any mistake or any opinion you might want to share.
Alejandro
You can contact me on Linkedin or follow me on Github. I am always up for a good discussion.
Thank you for reading until the end. Please consider following the writer and this publication. Visit Stackademic to find out more about how we are democratizing free programming education around the world.
