Non-Divisible Subset Hackerrank problem solution coderinme

Solution of Non-Divisible Subset Hackerrank problem

Given a set, S, of n distinct integers, print the size of a maximal subset, S’, of S where the sum of any 2 numbers in S’ is not evenly divisible by k.
Input Format

The first line contains 2 space-separated integers, n and k, respectively.
The second line contains n space-separated integers (we’ll refer to the ith value as ai) describing the unique values of the set.


Constraints

  • 1<=k<=10
  • 1<=n<=10^5
  • 1<=ai<=10^9
  • All of the given numbers are distinct.

Output Format

Print the size of the largest possible subset (S’).

Sample Input

4 3
1 7 2 4

Sample Output

3

Explanation

The largest possible subset of integers is S’={1,7,4}, because no two integers will have a sum that is evenly divisible by k=3:

1+7=8, and 8 is not evenly divisible by 3.
1+4=5, and 5 is not evenly divisible by 3.
4+7=11, and 11 is not evenly divisible by 3.
The number 2 cannot be included in our subset because it will produce an integer that is evenly divisible by k=3 when summed with any of the other integers in our set:

1+2=3, and 3/3=1(remainder 0).
4+2=6, and 6/3=2(remainder 0).
7+2=9, and 9/3=3(remainder 0).
Thus, we print the length of S’ on a new line, which is 3.
Non-Divisible Subset

Solution in C++

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


int main() {
/* Enter your code here. Read input from STDIN. Print output to STDOUT */ 
int n,k,i,c=0;
cin>>n>>k;
int arr[n];
for(i=0;i<n;i++) {
cin>>arr[i];
}
int b[k];
for(i=0;i<k;i++) {
b[i]=0;
}
for(i=0;i<n;i++) {
b[arr[i]%k]+=1;
}
c=min(b[0],1);
for(i=1;i<k/2+1;i++) {
if(i!=k-i) {
c+=max(b[i],b[k-i]);
}
}
if(k%2==0) c++;
cout<<c;
return 0;
}

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

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) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int k = in.nextInt();
        int a[] = new int[n];
        int cnts[] = new int[k];
        for(int a_i=0; a_i < n; a_i++){
            a[a_i] = in.nextInt();
            cnts[a[a_i]%k]++;
        }
        int cnt = 0;
        for (int i=1;i<=k/2;i++) {
            if (2*i!=k) {
                cnt += Math.max(cnts[i],cnts[k-i]);
            }
        }
        if (k%2==0) {
            if (cnts[k/2]>0) {
                cnt ++;
            }
        }
        if (cnts[0]>0) {
            cnt ++;
        }
        System.out.println(cnt);
        
    }
}

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;
}

A web developer(Front end and Back end), and DBA at csdamu.com. Currently working as Salesforce Developer @ Tech Matrix IT Consulting Private Limited. Check me @about.me/s.saifi

One comment: On Non-Divisible Subset Hackerrank problem solution coderinme

Leave a reply:

Your email address will not be published.