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 <= 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.

1 thought on “Non – Divisible Subset – HackerRank Solution”

  1. What’s really missing from all of the versions of this I have seen, is an explanation of WHY the pieces of the solution are the right solution, what is the thinking begind the algorithm’s elements. Most coders will quickly realize that any proper solution will rely on Div/Mod math, and many will then realize that this problem is really not testing your coding ability, but is instead testing your ability to remember, or figure out, which Div/Mod mathematical principles and properties you need to recall in order to write a working solution in code. That’s the biggest problem, as many can’t recall the mathematical principles that might be applicable, and when reading some solutions the author splats a bunch of code with no comments and no narrative to explain how it is achieving being the solution. Coders offering solutions using single-letter variables that do not “self document” the code, doesn’t help the observer either – many solutions simply look like a bunch of abstract ‘mathesque’ expressions that lack context. This solution is likely right, in that it works, but the author really needs to walk the observer through _why_ it works, expression by expression, with comments, in-order for the learning opportunity to have value for the readers.

    Posting ‘solutions’ without contextual narrative can be, unfortunately, a little grandstanding: “See, I can do it, but you can’t, and here’s my solution without explanation just to rub your nose in it!”.

    So, let’s do better. Let’s comment our solutions and give the reader some meaningful narrative to learn from.

Leave a Comment

Your email address will not be published. Required fields are marked *