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("%dn", 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); });