# HackerRank ‘Non-Divisible Subset’ Solution

H
##### Short Problem Definition:

Given a set S of n distinct integers, print the size of a maximal subset S’ of S where the sum of any 2 numbers in S’ are not evenly divisible by k.

Non-Divisible Subset

##### Complexity:

time complexity is O(N)

space complexity is O(N)

##### Execution:

This is by all means not an easy task and is also reflected by the high failure ratio of the participants. For a sum of two numbers to be evenly divisible by k the following condition has to hold. If the remainder of N1%k == r then N2%k = k-r for N1+N2 % k == 0. Let us calculate the set of all numbers with a remainder of r and k-r and pick the larger set. If the remainder is half of k such as 2 % 4 = 2 or exactly k such as 4 % 4 = 0, just one number from each of these sets can be contained in S’.

##### Solution:
 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 `def` `solveSubset(S, k, n):` `    ``r ``=` `[``0``] ``*` `k` `    `  `    ``for` `value ``in` `S:` `        ``r[value``%``k] ``+``=` `1` `    `  `    ``result ``=` `0` `    ``for` `a ``in` `xrange``(``1``, (k``+``1``)``/``/``2``):` `        ``result ``+``=` `max``(r[a], r[k``-``a])` `    ``if` `k ``%` `2` `=``=` `0` `and` `r[k``/``/``2``]:` `        ``result ``+``=` `1` `    ``if` `r[``0``]:` `        ``result ``+``=` `1` `    ``return` `result` `    `  `n, k ``=` `map``(``int``, ``raw_input``().split())` `S ``=` `map``(``int``, ``raw_input``().split())` `print` `solveSubset(S, k, n)`

[rust]use std::io;

fn get_numbers() -> Vec<u32> {
let mut line = String::new();
line.split_whitespace().map(|s| s.parse::<u32>().unwrap()).collect()
}

fn calculate_nondivisible(a: Vec<u32>, n: usize, k: usize) -> u32 {
let mut result = 0;

let mut r = vec![0; k];
for val in a {
r[(val as usize)%k] += 1;
}

for idx in 1..(k+1)/2 {
result += std::cmp::max(r[idx as usize], r[(k-idx) as usize]);
}

if k % 2 == 0 && r[k/2] != 0 {
result += 1;
}
if r != 0 {
result += 1;
}

result
}

fn main() {
let line = get_numbers();
let a = get_numbers();

println!(“{}”, calculate_nondivisible(a, line as usize, line as usize) );
}
[/rust] 