0
$\begingroup$

Let there be a set of N numbers. Now we are given two values K and X. Now we pick exactly K different numbers. And the each of that number with the XOR of X and that number.We can perform these operation as many times .Finally we have to find the maximum sum of the numbers (After performing these operation)

I am not getting how to handle perform these operation as many times this.

Example:

Given set $A : \{10, 15, 20, 13, 2, 1, 44\}$

$K = 4,X = 14$

Pick the numbers on the position $1, 3, 5 $ and $6$, change the amount in $1 \to 10⊕14=4$, the amount in $3 \to 20⊕14=26$, the amount in $5 \to 2⊕14=12$ and the amount of in $6 \to 1⊕14=15$. Afterwards, $A=\{4,15,26,13,12,15,44\}$ and the total sum of elements of set $A$ is $129$, which is maximum possible.

$\endgroup$

1 Answer 1

1
$\begingroup$

Note that XORing a number twice with X is the same as doing nothing-it gets you back to the start. You can think of each number in your list as having two states, the original and the number after one XOR. In your example, the first number could be either $10$ or $4$.

If you do a number of passes, you can change any number of numbers (if $K$ is odd) or any even number of numbers (if $K$ is even) to their alternate versions. For example, you could choose $1,2,3,4$ the first time and $1,2,3,5$ the second to XOR just $4$ and $5$. This gives an algorithm. Compute the XOR of each number in your list with $X$. Subtract the original version from the XOR version. If $K$ is odd, invert the ones with positive differences. If $K$ is even and there are an even number of positive differences, those are the ones you want to XOR, so do them. If $K$ is even and there is an odd number, do the largest of the positive differences and check whether doing the smallest positive and smallest negative together shows a profit. If so, do it as well.

$\endgroup$
2
  • $\begingroup$ Why change any even number $\endgroup$
    – cattt
    Jun 16, 2019 at 17:00
  • $\begingroup$ That only applies if $K$ is even. I have updated. The number of flips that are canceled is even, so if $K$ is even the number of uncanceled flips is also even. $\endgroup$ Jun 16, 2019 at 18:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.