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 = kr for N1+N2 % k == 0. Let us calculate the set of all numbers with a remainder of r and kr 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();
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[(kidx) 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) );
}
[/rust]