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

|

794 Discussions

|

  • 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
}

  • mahmoud_elsonba1
     + 1 comment

    how is it possible to be a set of "Distinct" numbers and at the same time having two tens? what is the meaning of distinct here?