java - Find Non Divisible subset -

given set s, of n distinct integers, print size of maximal subset s', of s sum of 2 numbers in s' not evenly divisible k. n= number of items in array, k = number divided by. s = array

    eg: input stdin    10 5    770528134 663501748 384261537 800309024 103668401 538539662 385488901   101262949 557792122 46058493      eg: input stdin     4 3     1 7 2 4      explanation :      1+7 = 8 : 8 not evenly divisible     1+4 = 5 : 5 not evenly divisible     7+4 = 11: 11 not evenly divisible      1+2 = 3     2+4 =6     2+7 = 9      divisible 3, subset s' = {1,7,4) of size 3. 

code:

    public static void main(string[] args) {             scanner in = new scanner(system.in);              int n = in.nextint();              int k = in.nextint();              long arr[] = new long[n];              (int = 0; < n; i++) {                 arr[i] = in.nextint();             }               final set<long> subset = new linkedhashset<>();              (int = 0; < n; i++) {                  (int j = + 1; j < n; j++) {                      long sum = arr[i] + arr[j];                      if (sum % k != 0) {                          subset.add(arr[i]);                         subset.add(arr[j]);                     }                 }             }              system.out.println(subset.size());         } 

i getting right answer second input ie. 3. however, getting 9 first input, expecting spit out 6.

i cannot readily follow idea in algorithm. makes think should work?

instead here’s idea. rule 2 elements i , j base set cannot both go subset if (i + j) % k == 0. assuming , j both positive, same (i % k == 0 && j % k == 0) || % k + j % k == k. want group elements remainder modulus k. 2 such groups remainders r , k - r (1 <= r < k) can safely add 1 group subset, , want add larger of two. can additionally add 1 element group remainder 0 (not two, since sum divisible k). if k even, can add 1 element group remainder k / 2.

edit: code more precise, here goes:

// assume elements > 0 static set<integer> findlargestsubset(int k, int... basesetelements) {     list<integer> aslist = intstream.of(basesetelements).boxed().collect(collectors.tolist());     set<integer> baseset = new hashset<integer>(aslist);     int n = baseset.size();      // group elements set remainder modulus k     list<list<integer>> elementsbymodulus = new arraylist<>();     (int ix = 0; ix < k; ix++) {         elementsbymodulus.add(new arraylist<>());     }     (int : baseset) {         if (i <= 0) {             throw new illegalargumentexception("" + i);         }         elementsbymodulus.get(i % k).add(i);     }     set<integer> largestsubset = new hashset<>(n);     (int remainder = 1; remainder < (k + 1) / 2; remainder++) {         list<integer> groupr = elementsbymodulus.get(remainder);         list<integer> groupkminusr = elementsbymodulus.get(k - remainder);         // add larger group result         if (groupr.size() > groupkminusr.size()) {             largestsubset.addall(groupr);         } else {             largestsubset.addall(groupkminusr);         }     }     // add 1 element remainder 0 if     if (!elementsbymodulus.get(0).isempty()) {         largestsubset.add(elementsbymodulus.get(0).get(0));     }     // if k even, add 1 element remainder k / 2 if     if (k % 2 == 0 && !elementsbymodulus.get(k / 2).isempty()) {         largestsubset.add(elementsbymodulus.get(k / 2).get(0));     }     return largestsubset; } 

for first example in question gives [800309024, 557792122, 384261537, 538539662, 770528134, 101262949], hence size 6.