In this post, we will solve HackerRank Non-Divisible Subset Problem Solution.
Given a set of distinct integers, print the size of a maximal subset of $ where the sum of any 2 numbers in S’ is not evenly divisible by k.
Example
S = [19, 10, 12, 10, 24, 25, 22] k = 4
One of the arrays that can be created is S'[0] = [10, 12, 25]. Another is
S'[1] = [19, 22, 24]. After testing all permutations, the maximum length solution array has 3 elements.
Function Description
Complete the nonDivisibleSubset function in the editor below.
nonDivisibleSubset has the following parameter(s):
- int S[n]: an array of integers
- int k: the divisor
Returns
- int: the length of the longest subset of s meeting the criteria
Input Format
The first line contains 2 space-separated integers, n and k, the number of values in S and the non factor.
The second line contains n space-separated integers, each an S[i], the unique values of the
set.
Sample Input
STDIN Function ----- -------- 4 3 S[] size n = 4, k = 3 1 7 2 4 S = [1, 7, 2, 4]
Sample Output
3Explanation
The sums of all permutations of two elements from S = {1, 7, 2, 4} are:
1 + 7 = 8
1 + 2 = 3
1 + 4 = 5
7 + 2 = 9
7 + 4 = 11
2 + 4 = 6Only S’ = {1, 7, 4} will not ever sum to a multiple of k = 3.
Non-Divisible Subset C Solution
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
#include <limits.h>
#include <stdbool.h>
int max(int a, int b){
if(a>b)return a;
return b;
}
int main(){
int n,a;
int k;
scanf("%d %d",&n,&k);
int residues[100];
for(int i=0;i<100;i++)residues[i]=0;
for(int a_i = 0; a_i < n; a_i++){
scanf("%d",&a);
residues[a % k]++;
}
int number=0;
if(residues[0]>0) number=1;
for(int i = 1; i < (k+1)/2; i++){
number+=max(residues[i],residues[k-i]);
}
if((k/2)*2==k && residues[k/2]>0)number++;
printf("%d\n",number);
return 0;
}Non-Divisible Subset C++ Solution
//Giorgi Kldiashvili
#include <bits/stdc++.h>
using namespace std;
int a[1020], n, k, x, answer;
int main()
{
scanf("%d%d", &n, &k);
for(int i=0;i<n;++i)
{
scanf("%d", &x);
a[x % k]++;
}
for(int i=1;i<k;++i)
{
if(i >= k - i)
break;
answer += max(a[i], a[k - i]);
}
if(a[0] != 0)
answer++;
if(a[k / 2] != 0 && k % 2 == 0)
answer++;
cout<<answer<<endl;
}Non-Divisible Subset C Sharp Solution
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
class Solution {
static void Main(String[] args) {
int[] nk = Array.ConvertAll(Console.ReadLine().Split(' '), Int32.Parse);
int[] numbers = Array.ConvertAll(Console.ReadLine().Split(' '), Int32.Parse);
Dictionary<int, int> remainderCount = new Dictionary<int, int>();
int k = nk[1];
int currentRemainder;
foreach(int n in numbers) {
currentRemainder = n % k;
if (remainderCount.ContainsKey(currentRemainder)) {
// 2 numbers with remainder 0 will satisfy division by key so we can take only one
remainderCount[currentRemainder] = currentRemainder == 0 ? 1 : remainderCount[currentRemainder] + 1;
} else { remainderCount.Add(currentRemainder, 1); }
}
// Add 1 zero if exists
int numOfElements = remainderCount.ContainsKey(0) ? remainderCount[0] : 0;
int r;
for (r = 1; r * 2 < k; r ++) {
numOfElements += Math.Max(remainderCount.ContainsKey(r) ? remainderCount[r] : 0,
remainderCount.ContainsKey(k - r) ? remainderCount[k - r] : 0);
}
if (r * 2 == k ) { numOfElements++; }
Console.WriteLine(numOfElements);
/*
foreach(int key in remainderCount.Keys) {
Console.WriteLine(key);
}
foreach(int key in remainderCount.Values) {
Console.WriteLine(key);
}
*/
}
}Non-Divisible Subset Java Solution
import java.io.*;
import java.util.*;
import java.lang.Math;
public class Solution {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int N = input.nextInt();
int K = input.nextInt();
int nonDivisibleSubsetCardinality = 0;
int[] modulusBuckets = new int[K];
//Place the values in buckets based on mod K
for(int i = 0; i < N; i++)
{
int bucket = input.nextInt() % K;
modulusBuckets[bucket] += 1;
}
//Adds 1 if there is only 1 element in the 0 bucket or the k/2 bucket because these are edge cases
nonDivisibleSubsetCardinality += (modulusBuckets[0] >= 1) ? 1 : 0;
nonDivisibleSubsetCardinality += (K%2 == 0 && modulusBuckets[K/2] >= 1) ? 1 : 0;
//Determine the max buckets we can use
int maxBuckets = 0;
if(K%2 == 0)
{
maxBuckets = (K/2)-1;
}
else
{
maxBuckets = K/2;
}
//Picks the biggest bucket of each pair for each even sum group
for(int i = 1; i <= maxBuckets; i++)
{
nonDivisibleSubsetCardinality += Math.max(modulusBuckets[i], modulusBuckets[K-i]);
}
System.out.println(nonDivisibleSubsetCardinality);
}
}Non-Divisible Subset JavaScript Solution
function processData(input) {
var inputs = input.split('\n');
var config = inputs[0];
var vals = inputs[1].split(' ');
var k, i;
config = config.split(' ');
k = config[1];
var count = 0;
var rems = Array(Number(k)).fill(0);
var mods = Array(vals.length).fill(0);
for (i = 0; i < vals.length; i++) {
mods[i] = vals[i] % k;
}
for (i = 0; i < k; i++) {
for (var j = 0; j < vals.length; j++) {
if (mods[j] === i) rems[i]++;
}
}
for (i = 1; i < Math.ceil(k / 2); i++) {
count = count + Math.max(rems[i], rems[k - i]);
}
if (k % 2 === 0) {
if (rems[k / 2] !== 0) count++;
}
if (rems[0] !== 0) count++;
console.log(count);
}
process.stdin.resume();
process.stdin.setEncoding("ascii");
_input = "";
process.stdin.on("data", function(input) {
_input += input;
});
process.stdin.on("end", function() {
processData(_input);
});Non-Divisible Subset Python Solution
import math
dummy, bucket_num = [ int(e) for e in input().strip().split() ]
nums = [ int(e) for e in input().strip().split() ]
if bucket_num == 1:
print(1)
else:
buckets = {}
for n in range(bucket_num):
buckets[n] = 0
for n in nums:
buckets[n%bucket_num] += 1
answer = 1 if buckets[0] > 0 else 0
for bucket in range(1, math.ceil(bucket_num//2)+1):
if buckets[bucket] > buckets[bucket_num-bucket]:
answer += buckets[bucket]
else:
answer += buckets[bucket_num-bucket]
if bucket_num//2 == bucket_num/2:
answer -= buckets[bucket_num/2]
if buckets[bucket_num/2] > 0:
answer += 1
print(answer)Other solutions
