My approach was to make an array called ‘delta’ which will contain all the differences between the elements of original array and after XORing them with X. After that I will sort that delta array in descending order. Then obviously , positive values (if any) will come before the negative ones/zeros. Therefore problem will then be divided into 2 cases:
1. When number of +ve values is divisible by K.
This means that I can XOR all those elements which will result in an increment over the initial sum.
2. When number of positive values is not divisible by K
This means there is a fixed number of positives that I can include . For clarity lets say number of positives can be written as QK+R, and R>0, then obviously, atleast QK values can contribute to the final sum, and lets call it fixed sum. The we have a decision to make for next K-R values, which are in negative region!.
From here on , we can have do three things,
Either take remaining R values plus K+R elements after the positives.
Or, take remaining R values plus excluding K+R previous elements. (unXoring basically)
Or else, don’t take either and stay with the fixed increment we had earlier.
Maximum of above will be our answer.
3. When number of positive values is less than K
This will be simple either or situation, either we take all or none, hence maximum of initial sum + first K values and just initial sum.
Hence I should be good to go, but sadly not even a single test case passed:sleepy: , so either I have misunderstood a problem or there is a big flaw in the logic , but i wasn’t able to find any test cases failing it.
A dry run of my approach on example test cases:
2
5
1 2 3 4 5
2
4
Delta Array (Sorted) : 4 4 4 -4 -4
So incremental value = 4+4+4-4=8 (number of inclusives is multiple of 2)
and adding it to original => 15 + 8 = 23
7
10 15 20 13 2 1 44
4
14
Delta Array (Sorted) : 14 10 6 -6 -10 -10 -14
So incremental value = 14+10+6-6=24
and adding it to original => 105+24 = 129
We create a new array, where we store the effect we have on a number when we xor it with ‘x’ (b[i]= a[i]-a[i]^x) . Xor any number with ‘x’ 2 times/even number of times and you get the same result …a[i]^x^x…(even number of times)=a[i].
if k is odd, answer is the sum of all positive numbers;
if k is even and there are even number of positive numbers in the array; answer is same as above.
if k is even,and number of positive numbers is odd, then answer is max(positive sum-smallest positive number,positive_sum+smallest negative number ). Hope this helps !!!
One can think of this in terms of a matrix almost, where each row is ok K size and denotes the operation of selection of bags.
Now each bag can only exist in two states: A[i] or A[i]^X. Which state it is in depends on how many times an operation has been performed on it. If even then A[i] else A[i]^X.
Say I have named bags such that 0 and 1 are positive and 2,3 are zero or negative.
If K=3 I can make this sequence of commands to select any one bag to change.
1 2 0
2 3 0
3 1 0
Notice that 1,2,3 appear twice while 0 appears thrice. So zero’s state is flipped.
Now to select one,
0 2 1
2 3 1
3 0 1
Similarly now only 1’s state is flipped. This always works because we are fixing 1 element and so our changing matrix has k-1 columns. Each column only has an element once so each element is there k-1 times. when k is odd, k-1 is even and so each element gets an even number of operations performed on it and thus no state change.
When K is even, I can select only two elements to flip at a time. Illustration:
K=4,
1 2 3 0
2 3 4 0
3 4 1 0
Here 0 and 3 are selected but there’s nothing special about 3 you can just swap all 3’s with 1’s and all 1’s with 3’s to select 0 and 1.
So now only pairs can be selected and if number of positives is even then I can select all of them, otherwise i’ll have to select one less or one extra.
It’s not the best but it helped me wrap my head around the problem…
suppose k = 3 and positive values are 7 ( lets say 1,2,3,4,5,6,7)
now take the sequence of (1,2,3) -> (4,5,3) making contribution of 3 zero as it is xor-ed 2 times then again take (3,6,7)
This makes it all positive.
You can try out similarly this way. the idea is to making the contribution of even xor-ed elements to k so that they can be taken all at a time.
For k = odd case :-
lets take k+1 numbers (k<n), out of these, choose one number, say x, now we have
k remaining numbers. Use the flipping operation k times and include x in all k operations,
so we will have k*(k-1) places left (as one position is occupied by x in all k operations).
We can now use k remaining numbers (excluding x) k-1 times each in above operations.
As k is odd, value of x is changed and as k-1 is even, the remaining k elements remain unchanged.
Hence as long as n >= k+1 we can always flip all the numbers by utilizing above method
to change one number at a time.
Thanks to cheerioskun I was able to come up with this proof.
(b[i]= a[i]-a[i]^x) . Xor any number with ‘x’ 2 times/even number of times and you get the same result 
!