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/