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
Please help me out !