public static int nonDivisibleSubset(int k, List<int> s)
   {
    int[] remainders = new int[k];

    foreach (int num in s)
    {
        int remainder = num % k;
        remainders[remainder]++;
    }

    int count = Math.Min(remainders[0], 1);

    for (int i = 1; i <= k / 2; i++)
    {
        if (i != k - i)
        {
            count += Math.Max(remainders[i], remainders[k - i]);
        }
        else if (remainders[i] > 0)
        {
            count++;
        }
    }

    return count;
}

int nonDivisibleSubset(int k, vector<int> s) {
    vector<long> arr(k,0);
    for(int i = 0; i < s.size(); i++){
        arr[s[i] % k]++;
    }
    long sum = 0;
    if (k == 1){sum = 1; goto END;}
    if (k == 2){sum = 2; goto END;}
    if (k % 2 == 0){
        if (arr[0] > 1) sum = sum + 1;
        if (arr[k/2] > 1) sum = sum + 1;
        for (long i = 1; i < k/2; i++){
            if (arr[i] > arr[k-i]){sum = sum + arr[i];}
            else {sum = sum + arr[k-i];}
        }    
    }
    else {
        if (arr[0] > 1) sum = sum + 1;
        for (long i = 1; i < (k+1)/2; i++){
            if(arr[i] > arr[k-i]){sum = sum + arr[i];}
            else {sum = sum + arr[k-i];}
        }
    }
    END:
    return sum;
}

        // k = 4, s = [1 1 1 2 2 3 3 3 3 4 4]
        // only 3 cases:
        // 1) we have 4 in s, we can take only one
        // 2) we can take only one 2, if it  exists
        // 3) we can take 1 or 3, but not together, 
        //    4 of "3" is bigger than 3 of "1", we take 4 of "3"
        int res = 0;
        
        int[] modK = new int[k];
        
        for (int el : s) {
            modK[el % k]++;
        }
        
        // we can take only one 4 if it exists
        if (modK[0] > 0) {
            res = 1;
        }
        
        // start with 1 because we counted modK[0] before
        for (int i = 1; i < k; i++) {
            // if no numbers, just miss
            if (modK[i] == 0) {
                continue;
            }
            
            // we can take only one 2 if it exists
            if (2 * i == k) {
                res++;
            } else {
                // we take 4 of "3", because it is bigger than 3 of "1"
                res += Math.max(modK[i], modK[k - i]);
								 // make them zero, not to count twice
                modK[i] = 0;
                modK[k - i] = 0;
            }
        }
        
        return res;

def nonDivisibleSubset(k, s):
    if k ==1: return 1 #first exception
    res = [x%k for x in s] #array of residues mod k
    recurrence = dict([(x,0) for x in range(k)]) #dict for saving recurrence of residues in array s
    for i in range(len(res)):
        recurrence[res[i]] += 1
    result = 0
    if recurrence[0]>0: result += 1 #Add one multiple of k, if exists

    if k <=3:#Two more special cases
        if k == 2 and recurrence[1]: result += 1
        else: result += max(recurrence[1],recurrence[2])
        return result
    
    for x in range(1,k//2): result += max(recurrence[x],recurrence[k-x])
        
    if k%2 == 0 and recurrence[k/2] > 0: result += 1
    else: result += max(recurrence[k//2],recurrence[k - k//2])

    return result