2
$\begingroup$

we are given an Array

Array size <= 10^4 .

0 <= A[i] <= 15

We need to partition the array into 4 subsets (each subset can have zero or more elements ). Take xor of each subset and sum those xors.

for example, one subset could have indices 0, 3, and 7, and another subset could have indices 1, 2, and 4 find the max sum.

4^n approach is very expensive.

there are only 16 different values of xor so for each value of xor=X we can search in array if is it possible to partition the array such that we get xor=X.

$\endgroup$
6
  • 1
    $\begingroup$ Have you tried dynamic programming? $\endgroup$ Oct 5, 2019 at 0:27
  • $\begingroup$ Does each part have to be from a contiguous/consecutive part of the array? You might find cs.stackexchange.com/tags/dynamic-programming/info helpful. $\endgroup$
    – D.W.
    Oct 5, 2019 at 6:22
  • $\begingroup$ Hint: with n array elements this is very easy to do in O(n). $\endgroup$
    – gnasher729
    Oct 5, 2019 at 7:32
  • $\begingroup$ @D.W. No. We need to divide the array into 4 subsets. each subset can have zero or more elements. $\endgroup$
    – user102578
    Oct 5, 2019 at 12:55
  • $\begingroup$ @YuvalFilmus can you elaborate? $\endgroup$
    – user102578
    Oct 5, 2019 at 12:55

1 Answer 1

1
$\begingroup$

For every $i \in \{0,\ldots,n\}$ (where $n$ is the length of the array) and for every $a,b,c \in \{0,\ldots,15\}$, we determine whether it is possible to partition the first $i$ elements of the array into four subsets, the first three of which XOR to $a,b,c$, respectively. We also compute the XOR of the entire array. Using the information for $i = n$, we can determine the possible XORs resulting from partitions of the array into four subsets, and so calculate the maximum sum. The resulting algorithm runs in linear time.

$\endgroup$
4
  • $\begingroup$ I think there should be an alternative algorithm if the elements are allowed to be large. $\endgroup$
    – gnasher729
    Oct 6, 2019 at 17:27
  • $\begingroup$ @YuvalFilmus Can you give a small example? $\endgroup$
    – user102578
    Oct 12, 2019 at 13:24
  • 1
    $\begingroup$ It's best if you programmed it on your own. $\endgroup$ Oct 12, 2019 at 14:26
  • $\begingroup$ … that way you learn, and Yuval has time to answer more questions. $\endgroup$
    – gnasher729
    Aug 20, 2023 at 11:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.