Online Assessment

Given an array A of size N. You need to find the maximum  XOR of a subset of A by choosing at most N/2 elements. The chosen elements need not be consecutive.  

Input Example1:

N=6,  A=[1,2,3,4,5,6]

Choosing 3 and 4 as a subset will result in xor of 7 which is the maximum. You need to return 7.

Input Example2: 

N = 4, A = [1, 2, 4, 7]
Output: 7

The constraints were as follows;
Also, it is given that N will be even only.
1 Like

For Every index find Dp[i][j] where i is index and j ranges from 1to N/2
and value stored will be maximum XOR

dp[i][j]= Max(dp[i-1][j],dp[i-1][j-1]^A[i])

I did the same but it did not pass all the test cases.
same doubt asked here

maybe you have to use xor basis on this, find set of basis vectors, then check for every num from 0 to 10^6 if you can form that by using atmost n/2 basis vectors. Check this blog : A Beautiful Technique for Some XOR Related Problems - Codeforces. Iā€™m not sure about this but its worth a try.

how many test cases it passed?