 Subset with no pair sum divisible by K (GeeksForGeeks)

#1

Can anyone please help me understand the solution to this problem as the geeksforgeeks explanations is not clear to me especially this part

" In below code array numbers with remainder 0 and remainder K/2 are handled separately. If we include more than 2 numbers with remainder 0 then their sum will be divisible by K, so we have taken at max 1 number in our consideration, same is the case with array numbers giving remainder K/2. "

#2

First, you store given array after taking modulo by k. ( If sum of two numbers is divisible by k, sum of their modulo will also be divisible by k).

To include maximum numbers, we can either take number of form i or k-i. We can’t take numbers of both types as their sum will be divisible by k.

Special cases:
Now if we include two zeros, then their sum will be zero, which is divisble by k. Hence, we will include at max one zero.
Same goes for k/2. If we include two k/2, then their sum will be k, which is divisble by k. Hence, we will include at max one k/2.

#3

@marksman

Why we are doing these steps like initializing res = min(f, 1) and for loop till K/2 only …??

`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`

`int` `res = min(f, 1);`

`// Choose maximum of count of numbers`

`// giving remainder i or K-i`

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

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

#4
• res = min(f, 1)

Now if we include two zeros, then their sum will be zero, which is divisble by k. Hence, we will include at max one zero.

The res = min(f, 1) will give output zero if no number is divisible by k in initial array (i.e. f=0) else 1.
Hence, it ensures that we include at max one number divisible by k.

• loop till K/2 only

To include maximum numbers, we can either take number of form i or k-i

We run a loop from i=1 to i<=k/2 and pick the maximum of f[i] and f[k-i].
If we run loop till k, then we will pick up extra numbers. For example:
k=8
Value of i and (k-i) will be
1 7
2 6
3 5
4 4
5 3
6 2
7 1
See that pair of values start repeating after i=k/2. Hence we run loop till i<=k/2 only.

#5

@marksman Thanks bro for you help 