We have been given an array of size n , and two integers k and x;
Now, We can perform the following operation any number of times (including zero):
1.Pick exactly k elements from array.
2.Xor the k chosen elements with x in the array.
Each element may be picked any number of times in different operations.
We have to find maximum sum of array we can have at the end if we perform the operations optimally.
Please help me out in these guys.
I have absolutely no clue.
what does xor do to a number's value?
its a fancy bit-flipper. So you want to flip high order bits from 0 to 1. as many as you can without making numbers smaller.
but there is a monkey wrench: they are integers you said, not unsigned integers, so some bit flips will make negative numbers which will decrease your sum. You want to avoid that as well.
again, its a bit flipper. ignoring negatives now, its still the same... just easier.
sort the input. while your xor flips high order bits for more than 50% of the next K, do it. unclear to me, do you resort and repeat or proceed until the while exits, then resort and repeat until the first K can't be improved? Are these integers bucket sortable (that tends to beat std::sort)? If not, is a 'already almost sorted' algorithm faster (eg shell sort is faster the closer arrays are to already sorted)? something like this? Tweaking the sort is optional as it takes unusual data to beat std::sort. Its really only worth it if you can bucket, because that gives you lift twice for repeats (repeated values check once for xor better is more efficient as it can skip the duplicates easier).