HackerRank Non-Divisible Subset problem solution

In this HackerRank Non-Divisible Subset problem you have Given a set of distinct integers, print the size of a maximal subset of S where the sum of any 2 numbers in S' is not evenly divisible by k.

Problem solution in Python programming.

from collections import defaultdict

n, k = [int(item) for item in input().strip().split()]
S = [int(item) for item in input().strip().split()]
mods = [item % k for item in S]
freqs = defaultdict(int)
for elem in mods:
    freqs[elem] += 1
total = 0
for key, val in freqs.items():
    if val == 0:
        continue
    if key == 0:
        total += 1
    elif (k - key) == key:
        total += 1
    elif key > (k - key):
        if (k - key) in freqs:
            total +=  max([val, freqs[k - key]])
        else:
            total += val
    elif key < (k - key):
        if (k - key not in freqs):
            total += val

print(total)

Problem solution in Java Programming.

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int k = in.nextInt();
        int a[] = new int[k];
        for(int i=0; i < n; i++){
            int ai = in.nextInt();
            a[ai % k]++;
        }
        int count = 0;
        for (int i = 1; i < (k + 1) / 2; ++i) {
            count += Math.max(a[i], a[k - i]);
        }
        if (k % 2 == 0) {
            count += a[k / 2] > 0 ? 1 : 0;
        }
        count += a[0] > 0 ? 1 : 0;
        
        System.out.println(count);
    }
}

Problem solution in C++ programming.

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;


int main() {
    int n, k; cin >> n >> k;
    vector<int> q(k);
    for (int i = 0; i != n; ++i) {
        int x; cin >> x;
        q[x % k] += 1;
    }
    int rv = min(1, q[0]);
    for (int i = 1; 2*i <= k; ++i) {
        int j = (k - i) % k;
        if (i == j) {
            rv += min(1, q[i]);
        } else {
            rv += max(q[i], q[j]);
        }
    }
    cout << rv << '\n';
    return 0;
}

Problem solution in C programming.

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

int main() {
    int n;
    int k;
    int a[101] = {};
    scanf("%d", &n);
    scanf("%d", &k);
    for (int i = 0; i < n; i++) {
        int tmp;
        scanf("%d", &tmp);
        a[tmp % k]++;
    }
    int count = 0;
    if (a[0] > 0)
        count++;
    if (k % 2 == 0 && a[k / 2] > 0)
        count++;
    for (int i = 1, j = k - 1; i < j; i++, j--) {
        if (a[i] > a[j])
            count += a[i];
        else
            count += a[j];
    }
    printf("%d\n", count);
    return 0;
}

Problem solution in JavaScript programming.

function processData(input) {
  //Enter your code here
  var temp = input.split('\n');
  var nk = temp[0].split(' ').map(Number), n = nk[0], k = nk[1];
  var arr = temp[1].split(' ').map(Number);
  var factorArray = Array(k).fill(0);
  for (let i = 0; i < n; i += 1) {
    factorArray[arr[i] % k] += 1;
  }
  let size = 0;
    
  for (let i = 0; i < Math.floor(k/2)+1; i += 1) {
    if (i == 0 || k == i * 2) {
      size += (factorArray[i] != 0) ? 1 : 0;
    } else {
      size += Math.max(factorArray[i], factorArray[k - i]);
    }
  }
  console.log(size);
} 

process.stdin.resume();
process.stdin.setEncoding("ascii");
_input = "";
process.stdin.on("data", function (input) {
    _input += input;
});

process.stdin.on("end", function () {
   processData(_input);
});