5
$\begingroup$

The problem:

We are given an array $A$, an integer $Z$ and a value $Q$. The goal is to maximize the sum of $A$, by performing following operation any number of times: We can select exactly $Z$ elements from the given array and perform XOR on each of them with $Q$.

Is there any data structure I can use which can perform this efficiently or any algorithm I am not aware of?

I tried finding each element's maximum possible value (using XOR/ignoring it), sorting the array and then making the selection but it did not work, which leads me to believe that the greedy approach won't work here.

I am primarily looking for an algorithm that can help or a data structure, not necessarily the code.

For example, given the array $[1, 2, 3, 4, 5], Z = 2$ and $Q = 4$, the answer is 23 as I can take XOR of 1 and 2 with 4 and of 3 and 4 with 4 as well.

Edit: The sum 23 is obtained as follows: We need to select Z (2) values at a time. So we select 1 and 2 and obtain their XOR with Q(4), which makes it 5 and 6. We then select 3 and 4 and obtain their XOR with Q, which makes them 7 and 0. Thus the final array becomes $[5,6,7,0,5] which is equal to 23 and is maximum possible sum.

$\endgroup$
  • $\begingroup$ Can you please add detail to either the description of how to compute the sum of $A$ or spell out how to arrive at 23? $\endgroup$ – greybeard Jun 10 at 15:55
  • $\begingroup$ Sure. I'll do that. $\endgroup$ – user106323 Jun 10 at 16:35
  • 1
    $\begingroup$ Should get interesting for $Z \in 2 \mathbb N +1$. $\endgroup$ – greybeard Jun 10 at 18:09
1
$\begingroup$

First, note that for any $a$, since XOR is associative:

$$(a \oplus b) \oplus b = a \oplus (b \oplus b)$$

Since $b \oplus b$ is $0$ and $0$ is neutral for XOR, we get that:

$$(a \oplus b) \oplus b = a \oplus (b \oplus b) = a \oplus 0 = a$$

In other words, there is no point performing XOR operation more than twice, for any $a$ with any $Q$. You can either XOR once, or not XOR at all (XOR twice)


Now, suppose you have an array $A$. Prepare the array $B$ as an array of the difference between $A$ before and after we XOR it:

$B_i = \max\{0, A_i \oplus Q - A_i\} $ (Since performing XOR on $A_i$ twice yields $A_i$, we can also choose $A_i$ itself).

Preparing $B$ takes $O(n)$.

Increasing the sum of $A$ is now equivalent to selecting the $Z$ XORS that their sum - difference is greatest, which is equivalent to selecting $Z$ max elements from $B$.

For that, there's a better solution than sorting ($O(n\log n)$):

  • Select the $Z-th$ largest element of $B$ using selection algorithm
  • Sweep $B$ and save any element that is larger than the $Z-th$ largest element

The indices of the elments chosen in $B$ determine both the elements of $A$ you select, and the XOR performed (or not performed). In total, it took $O(n)$ time.

$\endgroup$
  • $\begingroup$ Could you explain your algorithm on the example I have specified? Its somewhat unclear. $\endgroup$ – user106323 Jun 10 at 9:37
  • $\begingroup$ Which part of the algorithm is unclear to you? $\endgroup$ – lox Jun 10 at 10:24
  • $\begingroup$ The last part. Post making array B, I am supposed to select Z max elements from it right? And then do what with them? $\endgroup$ – user106323 Jun 10 at 14:10
  • $\begingroup$ That selection defines the elements from $A$ that you would select, and whether or not you XOR them. Suppose from $B$ you chose $[2,4,5]$, then elements $A_2$, $A_4$, $A_5$ are selected from $A$. Whether or not to XOR them you find easily in $O(1)$ by asking whether $B_i = 0$. $\endgroup$ – lox Jun 10 at 14:44
  • $\begingroup$ Also, as per my understanding of this algorithm, it fails for [10, 15, 20, 13, 2, 1, 44] when Z = 4 and Q = 14. $\endgroup$ – user106323 Jun 10 at 14:44

Your Answer

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