HackerRank ‘Non-Divisible Subset’ Solution

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


time complexity is O(N)

space complexity is O(N)


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

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)

use std::io;

fn get_numbers() -> Vec<u32> {
    let mut line = String::new();
    io::stdin().read_line(&mut line).ok().expect("Failed to read line");
    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] != 0 {
        result += 1;

fn main() {
    let line = get_numbers();
    let a = get_numbers();
    println!("{}", calculate_nondivisible(a, line[0] as usize, line[1] as usize) );

If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.


    The problem doesn’t say the maximum number of values in S’ is two.