HackerRank Non-Divisible Subset Problem Solution

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

Explanation
The sums of all permutations of two elements from S = {1, 7, 2, 4} are:

Only S’ = {1, 7, 4} will not ever sum to a multiple of k = 3.

HackerRank Non-Divisible Subset Problem Solution

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)