In this post, we will solve Non – Divisible Subset HackerRank Solution. This problem (Non – Divisible Subset) is a part of HackerRank Ruby series.
Contents
Task
Given a set of distinct integers, print the size of a maximal subset of S where the sum of any 2 numbers in S’ is not evenly divisible by k.
Example
 S = [19, 10, 12, 10, 24, 25, 22] k = 4
One of the arrays that can be created is S‘[0] = [10, 12, 25]. Another is S‘[1] = [19, 22, 24]. After testing all permutations, the maximum length solution array has 3 elements.
Function Description
Complete the nonDivisibleSubset function in the editor below.
nonDivisibleSubset has the following parameter(s):
- int S[n]: an array of integers
- int k: the divisor
Returns
- int: the length of the longest subset of S meeting the criteria
Input Format
The first line contains 2 space-separated integers, n and k, the number of values in S and the non factor.
The second line contains n space-separated integers, each an S[i], the unique values of the set.
Constraints
- 1 <= n <= 105
- 1 <= k <= 100
- 1 <= S[i] <= 109
- All of the given numbers are distinct.
Sample Input
STDIN Function
----- --------
4 3 S[] size n = 4, k = 3
1 7 2 4 S = [1, 7, 2, 4]
Sample Output
3
Explanation
The sums of all permutations of two elements from S = {1, 7, 2, 4} are:
Only S‘ = {1, 7, 4} will not ever sum to a multiple of k = 3.
Solution – Non – Divisible Subset – HackerRank Solution
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; }
Python
#!/bin/python3 # try a dumb bruteforce import sys from itertools import combinations def check_array(k, arr): for el1 in arr: test_arr = list(arr) test_arr.remove(el1) for el2 in test_arr: if (el1 + el2) % k == 0: return False return True def nonDivisibleSubset_brute(k, arr): if check_array(k, arr): return len(arr) best = 0 for num in range(1, len(arr)): to_remove = list(combinations(arr, num)) #print("to_remove = {}".format(to_remove)) for option in to_remove: test_arr = list(arr) #print("test_arr = {}".format(test_arr)) for el in option: test_arr.remove(el) if check_array(k, test_arr) == True: best = max(len(test_arr), best) return best def nonDivisibleSubset(k, arr): resid_cnt = [0] * k for el in arr: resid_cnt[el%k] += 1 res = min(1, resid_cnt[0]) for ind in range(1, (k//2)+1): if ind != k - ind: res += max(resid_cnt[ind], resid_cnt[k - ind]) if k % 2 == 0 and resid_cnt[int(k/2)] != 0: res += 1 return res 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)
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(); } }
Note: This problem (Non – Divisible Subset) is generated by HackerRank but the solution is provided by CodingBroz. This tutorial is only for Educational and Learning purpose.