WC 7.3 The Doctor's Dilemma

Dr. Shepherd has to pick some patients, among a set of patients having different survival rates, for his Alzheimer’s trial. As this selection is random, he decides to use a strategy for picking his patients. Given a set of N patients, Dr. Shepherd picks the maximum subset of patients where the sum of the survival rates of any 2 patients is not evenly divisible by k.
For example, consider the array of patients with survival rates N ={19,10,12,10,24,25,22} and k=4 . One of the sets that can be created is N’={10,12,25}. Another is N’={19,22,24} . After testing all permutations, the maximum length solution array has 3 elements.

Input Format
The first line contains 2 space-separated integers, m and k, the number of values in N and the non factor.
The second line contains m space-separated integers describing N[i], the unique values of the set.

Output Format
Print the size of the largest possible subset .

Sample Input
4 3
1 7 2 4

Sample Output
3

Explanation
The sums of all permutations of two elements from N={1,7,2,4} are:
1 + 7 = 8
1 + 2 = 3
1 + 4 = 5
7 + 2 = 9
7 + 4 = 11
2 + 4 = 6
We see that only N’={1,7,4} will not ever sum to a multiple of k=3 .

Testcases: link

This challenge is worth 80 points.

You must be logged in to submit a solution

View ranklist for this challenge
About scoring and submission

Contact Us


Kunal Desai : 7715051136

Neelraj Patil : 9930671144



Privacy Policy