#
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