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

|

795 Discussions

|

  • cherkashin_i_a
     + 0 comments
    import collections
def nonDivisibleSubset(k, s):
    counts = collections.Counter((i % k for i in s))
    return sum((max(counts[r], counts[k - r]) for r in range(k//2 + 1))) \
    + (1 - counts[0])*(0 in counts) \
    + (1 - counts[k // 2])*(k % 2 == 0)*(k // 2 in counts)

  • drkrob7865
     + 0 comments
    int nonDivisibleSubset(int k, vector<int> s) {
    vector<int> r(k);
    for (size_t i = 0; i < s.size(); i++) {
        r[s[i] % k]++;
    }
    r[k/2] = (k % 2 == 0) ? 1 : r[k/2];
    int c = (r[0] > 0) ? 1 : 0;
    for (size_t i = 1; i < k/2 + 1; i++) {
        c += (r[i] >= r[k-i]) ? r[i] : r[k-i];
    }
    return c;
}

  • mrweisu
     + 0 comments

    Python 3

    from math import floor

    def nonDivisibleSubset(k, s): # Write your code here

    s = [i % k for i in s]

freq = {i: 0 for i in range(k)}

for i in s:
    freq[i] += 1

ans = 0

for i in range(1, floor(k/2)+1):

    if i == k/2:
        continue

    if freq[i] >= freq[k-i]:
        del freq[k-i]
        ans += freq[i]
    else:
        del freq[i]
        ans += freq[k-i]

if k/2 in freq and freq[k/2] != 0:
    ans += 1

if freq[0] != 0:
    ans += 1

return ans

  • alex_k5
     + 0 comments
    def nonDivisibleSubset(k, s):
    remainders = Counter([i % k for i in set(s)])
    if k/2 in remainders:
        remainders[k/2] = 1
    if 0 in remainders:
        remainders[0] = 1
    even_div = [(x, y) for x, y in (combinations(remainders, 2)) if x + y == k]
    for i,j in even_div:
        remainders.pop(i if remainders[i] < remainders[j] else j)
    return sum(remainders.values())

  • stamatowsky
     + 0 comments
    fun nonDivisibleSubset(k: Int, s: Array<Int>): Int {
    val d = IntArray(k) {0}
    for (i in s.indices) {
        val rem = s[i] % k
        d[rem]++
    }
    
    val k2 = k / 2
    
    var r = Math.min(1, d[0])
    for (i in 1..k2) {
        if (k % 2 == 0 && i == k2) {
            r += Math.min(1, d[i])
        } else {
            val r1 = d[i]
            val r2 = d[k - i]
            val rm = Math.max(r1, r2)
            r += rm
        }
      
    }
    
    return r
}