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