# Data structure for selection of K elements and taking sum

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. • 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? – greybeard Jun 10 '19 at 15:55 • Sure. I'll do that. – user106323 Jun 10 '19 at 16:35 • Should get interesting for$Z \in 2 \mathbb N +1$. – greybeard Jun 10 '19 at 18:09 ## 1 Answer 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. • Could you explain your algorithm on the example I have specified? Its somewhat unclear. – user106323 Jun 10 '19 at 9:37 • Which part of the algorithm is unclear to you? – lox Jun 10 '19 at 10:24 • The last part. Post making array B, I am supposed to select Z max elements from it right? And then do what with them? – user106323 Jun 10 '19 at 14:10 • 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\$. – lox Jun 10 '19 at 14:44
• Also, as per my understanding of this algorithm, it fails for [10, 15, 20, 13, 2, 1, 44] when Z = 4 and Q = 14. – user106323 Jun 10 '19 at 14:44