Non-Divisible Subset

Given a set of distinct integers, print the size of a maximal subset of  where the sum of any  numbers in  is not evenly divisible by .

For example, the array  and . One of the arrays that can be created is . Another is . After testing all permutations, the maximum length solution array has elements.

Function Description

Complete the nonDivisibleSubset function in the editor below. It should return an integer representing the length of the longest subset of  meeting the criteria.

nonDivisibleSubset has the following parameter(s):

• S: an array of integers
• k: an integer

Input Format

The first line contains  space-separated integers,  and , the number of values in  and the non factor.
The second line contains  space-separated integers describing , the unique values of the set.

Constraints

• All of the given numbers are distinct.

Output Format

Print the size of the largest possible subset ().

Sample Input

4 3
1 7 2 4

Sample Output

3

Explanation

The sums of all permutations of two elements from  are:

1 + 7 = 8
1 + 2 = 3
1 + 4 = 5
7 + 2 = 9
7 + 4 = 11
2 + 4 = 6

We see that only  will not ever sum to a multiple of .

 php

<?php

/*

* Complete the 'nonDivisibleSubset' function below.

*

* The function is expected to return an INTEGER.

* The function accepts following parameters:

* 1. INTEGER k

* 2. INTEGER_ARRAY s

*/

function nonDivisibleSubset($K, $arr) {

$N = count($arr);

// Array for storing frequency of

// modulo values

$f = array_fill(0, $K, NULL);

// Fill frequency array with

// values modulo K

for ($i = 0; $i < $N; $i++)

$f[$arr[$i] % $K]++;

// if K is even, then update f[K/2]

if ($K % 2 == 0)

$f[$K / 2] = min($f[$K / 2], 1);

// Initialize result by minimum of 1 or

// count of numbers giving remainder 0

$res = min($f[0], 1);

// Choose maximum of count of numbers

// giving remainder i or K-i

for ($i = 1; $i <= $K / 2; $i++)

$res += max($f[$i], $f[$K - $i]);

return $res;

}

$fptr = fopen(getenv("OUTPUT_PATH"), "w");

$first_multiple_input = explode(' ', rtrim(fgets(STDIN)));

$n = intval($first_multiple_input[0]);

$k = intval($first_multiple_input[1]);

$s_temp = rtrim(fgets(STDIN));

$s = array_map('intval',

preg_split('/ /', $s_temp, -1, PREG_SPLIT_NO_EMPTY));

$result = nonDivisibleSubset($k, $s);

fwrite($fptr, $result . "\n");

fclose($fptr);