Subset with no pair sum divisible by K (GeeksForGeeks)

help

#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[0], 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[0], 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[0], 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[0], 1) will give output zero if no number is divisible by k in initial array (i.e. f[0]=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 :slight_smile: