We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Implementation
  4. Non-Divisible Subset
  5. Discussions

Non-Divisible Subset

Sort by

recency

|

815 Discussions

|

  • ds1b_1641540100
     + 0 comments

    Solution in Python 3

    #!/bin/python3
# try a dumb bruteforce

import sys
from itertools import combinations

def check_array(k, arr):
    for el1 in arr:
        test_arr = list(arr)
        test_arr.remove(el1)
        for el2 in test_arr:
            if (el1 + el2) % k == 0:
                return False
    return True

def nonDivisibleSubset_brute(k, arr):
    if check_array(k, arr):
        return len(arr)
    best = 0
    for num in range(1, len(arr)):
        to_remove = list(combinations(arr, num))
        for option in to_remove:
            test_arr = list(arr)
            for el in option:
                test_arr.remove(el)
            if check_array(k, test_arr) == True:
                best = max(len(test_arr), best)
    return best

def nonDivisibleSubset(k, arr):
    resid_cnt = [0] * k
    for el in arr:
        resid_cnt[el%k] += 1
    res = min(1, resid_cnt[0])
    for ind in range(1, (k//2)+1):
        if ind != k - ind:
            res += max(resid_cnt[ind], resid_cnt[k - ind])
    if k % 2 == 0 and resid_cnt[int(k/2)] != 0:
        res += 1
    return res
    
if __name__ == "__main__":
    n, k = input().strip().split(' ')
    n, k = [int(n), int(k)]
    arr = list(map(int, input().strip().split(' ')))
    result = nonDivisibleSubset(k, arr)
    print(result)

  • zettix1
     + 0 comments

    Wordy but get the job done.

    public static int nonDivisibleSubset(int k, List<Integer> s) {
    Map<Integer, Integer> modToCount = new HashMap<>();
    for (Integer q : s) {
        int r = q % k;
        int c = modToCount.getOrDefault(r, 0); 
        c++;
        modToCount.put(r, c); 
    }
    if (modToCount.containsKey(0)) {
        modToCount.put(0, 1); 
    }   
    if (k % 2 == 0 && modToCount.containsKey(k / 2)) {
        modToCount.put(k / 2, 1); 
    }   
    Set<Integer> skip = new HashSet<>();
    int count = 0;
    for (Integer rem : modToCount.keySet()) {
        if (skip.contains(rem)) {
            continue;
        }   
        int bad = k - rem;
        int val = modToCount.get(rem);
        if (modToCount.containsKey(bad)) {
            if (modToCount.get(bad) > val) {
                val = modToCount.get(bad);
            }   
            skip.add(bad);
        }   
        count += val;
    }   
    return count;
}

  • amit_kumar_mish2
     + 0 comments

    // Write your code here int arr[]=new int[k]; for(int i=0;i

    int max=Math.min(arr[0],1);

    for(int i=1;i<=k/2;i++) { if(i!=k-i) { max+=Math.max(arr[i],arr[k-i]); } else { max++; } } return max;

  • nickolayyegorov
     + 0 comments
    counts = [0] * k
for el in s: counts[el%k] += 1

res = min(counts[0], 1)
for i in range(1, k//2+1):
        res += 1 if (i == k-i) else max(counts[i], counts[k-i])

return res

  • anarod_val25
     + 0 comments

    The fact that the hardest part on this thing was remembering how mods work other than checking if smt is divisible xd

    int nonDivisibleSubset(int k, vector<int> s) {
    vector<int> mods(k, 0);

    for (int x : s) {
        mods[x % k]++;
    }

    int count = 0;

    if (mods[0] > 0) count++;

    for (int i = 1; i <= k / 2; i++) {
        if (i == k - i) {
            count++;
        } else {
            count += max(mods[i], mods[k - i]);
        }
    }

    return count;
}