Subset no pair sum divisible by k

#1

i am not able to understand the logic behind this question

#2

lets take an example,
arr[ ] = {3, 7, 2, 9, 1}
k = 3

now for a given set, 2^n subsets are possible. we have to find the biggest subset possible, in which the sum of each pair of elements is not divisible by k, ie 3 in this question.
some of the possible subsets of this array are {3, 7, 2, 9}, {3, 7, 1}, {2, 9, 1}, etc
now let us consider the subset {3, 7, 1}
the possible pairs in this subset are 3+7, 7+1 and 3+1
all of these pairs are indivisble by 3, hence this is an acceptable subset.
Let us consider another subset, {3, 7, 2, 1}
in this, the pair 1 + 2 is divisible by 3. the pair 7 + 2 is also divisible by 3
hence this subset is not acceptable,
it is observed that {3, 7, 1} is the biggest subset that satisfies the given conditions

so you basically have to make sure to not choose 2 numbers in a subset such that their sum is divisble by k. find all such possible subsets and report the biggest one as the answer.

#3

@suhailrashidsalma i hope i have solved your query. Please mark this doubt as resolved if you are satisfied.

#4

Hey Suhail since you are not responding to this thread I am marking your doubt as resolved for now. Please re-open it if required.

#5

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.