# Hackerrank Non-Divisible Subset Solution

.MathJax_SVG_Display {text-align: center; margin: 1em 0em; position: relative; display: block!important; text-indent: 0; max-width: none; max-height: none; min-width: 0; min-height: 0; width: 100%} .MathJax_SVG .MJX-monospace {font-family: monospace} .MathJax_SVG .MJX-sans-serif {font-family: sans-serif} .MathJax_SVG {display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 100%; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0} .MathJax_SVG * {transition: none; -webkit-transition: none; -moz-transition: none; -ms-transition: none; -o-transition: none} .mjx-svg-href {fill: blue; stroke: blue} .MathJax_SVG_LineBox {display: table!important} .MathJax_SVG_LineBox span {display: table-cell!important; width: 10000em!important; min-width: 0; max-width: none; padding: 0; border: 0; margin: 0}

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.MathJax_SVG_Display {text-align: center; margin: 1em 0em; position: relative; display: block!important; text-indent: 0; max-width: none; max-height: none; min-width: 0; min-height: 0; width: 100%} .MathJax_SVG .MJX-monospace {font-family: monospace} .MathJax_SVG .MJX-sans-serif {font-family: sans-serif} .MathJax_SVG {display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 100%; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0} .MathJax_SVG * {transition: none; -webkit-transition: none; -moz-transition: none; -ms-transition: none; -o-transition: none} .mjx-svg-href {fill: blue; stroke: blue} .MathJax_SVG_LineBox {display: table!important} .MathJax_SVG_LineBox span {display: table-cell!important; width: 10000em!important; min-width: 0; max-width: none; padding: 0; border: 0; margin: 0}

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.

Constraints.MathJax_SVG_Display {text-align: center; margin: 1em 0em; position: relative; display: block!important; text-indent: 0; max-width: none; max-height: none; min-width: 0; min-height: 0; width: 100%} .MathJax_SVG .MJX-monospace {font-family: monospace} .MathJax_SVG .MJX-sans-serif {font-family: sans-serif} .MathJax_SVG {display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 100%; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0} .MathJax_SVG * {transition: none; -webkit-transition: none; -moz-transition: none; -ms-transition: none; -o-transition: none} .mjx-svg-href {fill: blue; stroke: blue} .MathJax_SVG_LineBox {display: table!important} .MathJax_SVG_LineBox span {display: table-cell!important; width: 10000em!important; min-width: 0; max-width: none; padding: 0; border: 0; margin: 0}

• All of the given numbers are distinct.

Output Format.MathJax_SVG_Display {text-align: center; margin: 1em 0em; position: relative; display: block!important; text-indent: 0; max-width: none; max-height: none; min-width: 0; min-height: 0; width: 100%} .MathJax_SVG .MJX-monospace {font-family: monospace} .MathJax_SVG .MJX-sans-serif {font-family: sans-serif} .MathJax_SVG {display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 100%; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0} .MathJax_SVG * {transition: none; -webkit-transition: none; -moz-transition: none; -ms-transition: none; -o-transition: none} .mjx-svg-href {fill: blue; stroke: blue}

Print the size of the largest possible subset ().

Sample Input.MathJax_SVG_Display {text-align: center; margin: 1em 0em; position: relative; display: block!important; text-indent: 0; max-width: none; max-height: none; min-width: 0; min-height: 0; width: 100%} .MathJax_SVG .MJX-monospace {font-family: monospace} .MathJax_SVG .MJX-sans-serif {font-family: sans-serif} .MathJax_SVG {display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 100%; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0} .MathJax_SVG * {transition: none; -webkit-transition: none; -moz-transition: none; -ms-transition: none; -o-transition: none} .mjx-svg-href {fill: blue; stroke: blue}

4 3
1 7 2 4


Sample Output.MathJax_SVG_Display {text-align: center; margin: 1em 0em; position: relative; display: block!important; text-indent: 0; max-width: none; max-height: none; min-width: 0; min-height: 0; width: 100%} .MathJax_SVG .MJX-monospace {font-family: monospace} .MathJax_SVG .MJX-sans-serif {font-family: sans-serif} .MathJax_SVG {display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 100%; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0} .MathJax_SVG * {transition: none; -webkit-transition: none; -moz-transition: none; -ms-transition: none; -o-transition: none} .mjx-svg-href {fill: blue; stroke: blue}

3


Explanation.MathJax_SVG_Display {text-align: center; margin: 1em 0em; position: relative; display: block!important; text-indent: 0; max-width: none; max-height: none; min-width: 0; min-height: 0; width: 100%} .MathJax_SVG .MJX-monospace {font-family: monospace} .MathJax_SVG .MJX-sans-serif {font-family: sans-serif} .MathJax_SVG {display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 100%; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0} .MathJax_SVG * {transition: none; -webkit-transition: none; -moz-transition: none; -ms-transition: none; -o-transition: none} .mjx-svg-href {fill: blue; stroke: blue} .MathJax_SVG_LineBox {display: table!important} .MathJax_SVG_LineBox span {display: table-cell!important; width: 10000em!important; min-width: 0; max-width: none; padding: 0; border: 0; margin: 0}

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


We see that only  will not ever sum to a multiple of .

### Solution in java8

Approach 1.

import java.util.Scanner;

public class Solution {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);

int n = sc.nextInt();
int k = sc.nextInt();

int[] remainders = new int[k];
for (int i = 0; i < n; i++) {
int ai = sc.nextInt();
remainders[ai % k]++;
}

int result = 0;
for (int i = 0; i * 2 <= k; i++) {
int opposite = (k - i) % k;
if (i == opposite) {
result += Math.min(remainders[i], 1);
} else {
result += Math.max(remainders[i], remainders[opposite]);
}
}
System.out.println(result);

sc.close();
}
}

Approach 2.

import java.io.*;
import java.util.*;

public class Solution {

public static void main(String[] args) {
int res = 0;
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
int k = scan.nextInt();
int[] count = new int[k];
for(int i=0; i<n; i++){
count[scan.nextInt() % k]++;
}
if(count[0] != 0)
res++;
for(int i=1; i<(k/2 + 1); i++){
if(i == (k/2) && k%2==0){
res++;
break;
}
res += Math.max(count[i], count[k-i]);
}
System.out.println(res);
}
}

Approach 3.

import java.io.*;
import java.util.*;

public class Solution {

public static void main(String[] args) {

Scanner scan=new Scanner(System.in);
int n=scan.nextInt();
int k=scan.nextInt();
int[] rem=new int[k];
for(int i=0;i<n;i++)
{
int p=scan.nextInt();
rem[p%k]++;
}
int res=0;
if(k%2==0)
{
for(int l=1;l<k/2;l++)
{
res+=max(rem[l],rem[k-l]);
}
if(rem[0]>0)res++;
if(rem[k/2]>0)res++;
}
else
{
for(int l=1;l<=k/2;l++)
{
res+=max(rem[l],rem[k-l]);
}
if(rem[0]>0)res++;
}
System.out.println(res);

}
static int max(int a,int b)
{
if(a>b)
return a;
else return b;
}
}

### Solution in python3

Approach 1.


n, k = (int(i) for i in (input().strip().split()))

arr = [int(i) for i in (input().strip().split())]

def nonDevisibleSubset(arr, k):
counts = [0] * k
for n in arr:
counts[n % k] += 1

count = min(counts[0], 1)
for i in range (1, k // 2 + 1):
if i != k - i:
count += max(counts[i], counts[k - i])

if k % 2 == 0:
count += 1
print(count)

nonDevisibleSubset(arr, k)

Approach 2.

#!/bin/python3

import sys

def nonDivisibleSubset(k, arr):
counts = k * [0]
for i in arr:
counts[i % k] += 1

sum = 0
for i in range(1, (k+1)//2):
if counts[i] > counts[k-i]:
sum += counts[i]
else:
sum += counts[k-i]

if counts[0] > 0:
sum += 1
if k % 2 == 0 and counts[k//2] > 0:
sum += 1
return sum

if __name__ == "__main__":
n, k = input().strip().split(' ')
n, k = [int(n), int(k)]
arr = list(map(int, input().strip().split(' ')))
result = nonDivisibleSubset(k, arr)
print(result)


Approach 3.

#!/bin/python3

import sys

def nonDivisibleSubset(k, arr):
# Complete this function
counts = [0]*k
for i in range(len(arr)):
counts[arr[i]%k] = counts[arr[i]%k] + 1
count = min(counts[0], 1)
for i in range(1, (k//2)+1):
if(i != k-i):
count = count + max(counts[i], counts[k-i])
if(k%2 == 0):
count = count + 1
return count

if __name__ == "__main__":
n, k = input().strip().split(' ')
n, k = [int(n), int(k)]
arr = list(map(int, input().strip().split(' ')))
result = nonDivisibleSubset(k, arr)
print(result)


### Solution in cpp

Approach 1.

#include <iostream>

using namespace std;

long long n, k, x, i, sum, V[105];

int main()
{
cin>>n>>k;
for (i=1; i<=n; i++)
{
cin>>x;
V[x%k]++;
}
//imp + 0
for (i=1; i<=k/2; i++)
{
if (i==k-i)
sum++;
else
sum+=max(V[i], V[k-i]);
}
if (V[0]>0)
sum++;
cout<<sum;
return 0;
}


Approach 2.

#include <bits/stdc++.h>
using namespace std;
int c[110], n, k;
int main()
{
int i=0,a=0;
memset(c, 0, sizeof(c) );
scanf("%d%d", &n, &k);
while(i < n)
{
int x;
scanf("%d", &x);
x %= k;
c[x]++;
i++;
}
a += min(1, c[0]);
i=1;
while(i < k/2 + k%2)
{
a += max(c[i], c[k - i]);
i++;
}
if (k % 2 == 0)
a += min(1, c[k/2]);
cout<<a<<endl;
return 0;
}

Approach 3.

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

int main() {
int n,k;
cin>>n>>k;
vector<int> a(n);
vector<int> r(k);
for(int i=0;i<n;i++){
cin>>a[i];
a[i]%=k;
r[a[i]]++;
}
int ans=0;
for(int i=1;i<(k/2+k%2);i++){
ans+=max(r[i],r[k-i]);
}
ans+=!!r[0];
if(k%2==0) ans+=!!r[k/2];
cout<<ans<<endl;
return 0;
}