Non-Divisible Subset HackerRank Solution in C, C++, Java, Python

Given a set of distinct integers, print the size of a maximal subset of  where the sum of any  numbers in  is not evenly divisible by .

For example, the array  and . One of the arrays that can be created is . Another is . After testing all permutations, the maximum length solution array has  elements.

Function Description

Complete the nonDivisibleSubset function in the editor below. It should return an integer representing the length of the longest subset of  meeting the criteria.

nonDivisibleSubset has the following parameter(s):

• S: an array of integers
• k: an integer

Input Format

The first line contains  space-separated integers,  and , the number of values in  and the non factor.

The second line contains  space-separated integers describing , the unique values of the set.

Output Format

Print the size of the largest possible subset ().

Sample Input

4 3

1 7 2 4

 

Sample Output

3

 

Explanation

The sums of all permutations of two elements from  are:

1 + 7 = 8

1 + 2 = 3

1 + 4 = 5

7 + 2 = 9

7 + 4 = 11

2 + 4 = 6

 

Non-Divisible Subset HackerRank Solution in C

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
int main(){
    int n; 
    int k; 
    scanf("%d %d",&n,&k);
    
    int count[k];
    for (int i = 0; i < k; i++) {
        count[i] = 0;
    }
    
    for(int i = 0; i < n; i++){
        int a;
        scanf("%d",&a);
        count[a % k]++;
    }
    
    int max = 0;
    for (int i = 0; i <= k/2; i++) {
        if (i == 0 || i == k - i) {
            if (count[i] >= 1) {
                max += 1;
            }
        } else {
            max += count[i] > count[k-i] ? count[i] : count[k-i];
        }
    }
    printf("%d\n",max);
    
    return 0;
}

 

Non-Divisible Subset HackerRank Solution in C++

#include <cstdio>
#include <cstdlib>
#include <cassert>
#include <iostream>
#include <set>
#include <vector>
#include <cstring>
#include <string>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <complex>
#include <map>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
typedef vector<pii> vii;
typedef vector<string> vs;

int main() {
    int n,k;
    cin >> n >> k;
    vi a(n);
    vi c(k);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        ++c[a[i] % k];
    }
    int res = min(1, c[0]);
    for (int i = 1; 2*i < k; ++i) {
        res += max(c[i], c[k-i]);
    }
    if (k % 2 == 0) res += min(1, c[k/2]);
    cout << res << endl;
    return 0;
}

 

Non-Divisible Subset HackerRank Solution in Java

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) throws IOException{
        new Solution().run();
    }
    
    public void run() throws IOException{
        Scanner in = new Scanner(System.in);
        BufferedWriter log = new BufferedWriter(new OutputStreamWriter(System.out));
        int n = in.nextInt();
        int k = in.nextInt();
        
        int[]a = new int[n];
        int[]c = new int[k];
        
        for(int i=0;i<n;i++){
            a[i] = in.nextInt();
            a[i]=a[i]%k;
            c[a[i]]++;
        }
        
        int ans=0;
        ans+=(c[0]>0)?1:0;//good if 1 exists, cannot be more
        for(int i=1;i<=k-i;i++){
            if(i<k-i) {
                ans+=Math.max(c[i],c[k-i]);
            } else {//i==k-i
                ans+=(c[i]>0)?1:0;//not more possible
            }
        }
        log.write("" +ans+"\n"); 
        
        log.flush();
    }
}

 

Non-Divisible Subset HackerRank Solution in Python

rr = raw_input
rrM = lambda: map(int,rr().split())
N,K = rrM()
A = rrM()
S = [0 for _ in xrange(K)]
for i in A: S[i%K] += 1
ans = 0
for p in xrange(K/2 + 1):
    q = (K-p)%K
    if p==q: ans += 1 if S[p] else 0
    else: ans += max(S[p],S[q])
print ans

 

Non-Divisible Subset HackerRank Solution in C#

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
class Solution {

    static void Main(String[] args) {
        int k = int.Parse(Console.ReadLine().Split(' ').Last());
        int[] a = Console.ReadLine().Split(' ').Select(p => int.Parse(p)).ToArray();
        int[] mk = new int[k];
        for (int i = 0; i < a.Length; i++) mk[a[i] % k]++;
        long x = 0;
        if (mk[0] > 0) x++;
        for (int i = 1; i < (k + 1) / 2; i++)
            x += Math.Max(mk[i], mk[k - i]);
        if (k % 2 == 0 && mk[k / 2] > 0) x++;
        Console.WriteLine(x);
    }
}

 

Attempt Non-Divisible Subset HackerRank Challenge 

Link – https://www.hackerrank.com/challenges/non-divisible-subset/

Next HackerRank Challenge Solution 

Link – https://exploringbits.com/repeated-string-hackerrank-solution/