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. "
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.
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]);
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.
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.
