##### 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*.

##### Link

##### 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:

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; } result } 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.