Non – Divisible Subset – HackerRank Solution

In this post, we will solve Non – Divisible Subset HackerRank Solution. This problem (Non – Divisible Subset) is a part of HackerRank Ruby series.

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 <= 10⁵
• 1 <= k <= 100
• 1 <= S[i] <= 10⁹
• 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.