Online Assessment

general
1 
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;
1<N<120
1<=A[i]<=10^6
Also, it is given that N will be even only.
1 Like
2

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])

3

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

4

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.

5

how many test cases it passed?