Question

Khaled has an array A of N elements. It is guaranteed that N is even. He wants to choose at most N/2 elements from array A. It is not necessary to choose consecutive elements. Khaled is interested in the XOR of all the elements he chooses. Here, XOR denotes the bitwise XOR operation. For example, if A = [2, 4, 6, 8], then Khaled can choose the subset [2, 4, 8] to achieve XOR = (2 XOR 4 XOR 8) = 14. Khaled wants to maximize the XOR of all the elements he chooses. Your task is to help Khaled to find the max XOR of a subset, that he can achieve by choosing at most N/2 elements?​

Answer 1

Answer:

import java.util.*;

class Main {

   public static void main (String[]args)  

   {

       final int N = 120, M = 1 << 20;

       int dp[] = new int[M];

       char res[] = new char[M];

       Scanner sc = new Scanner (System.in);

       int n = sc.nextInt ();

       int arr[] = new int[n];

       for (int i = 0; i < n; i++)

           arr[i] = sc.nextInt ();

       for (int i = 1; i < M; i++)

           dp[i] = Integer.MAX_VALUE;

       for (int i = 0; i < n; ++i)

       {

           if (arr[i] == 0)

           continue;

           for (int j = 0; j < M; ++j)

           res[j] = 0;

           for (int k = 0; k < M; ++k)

       {

               if (res[k] == 1)

               continue;

               if (dp[k] > dp[k ^ arr[i]])

               dp[k] = dp[k ^ arr[i]] + 1;

            else if (dp[k ^ arr[i]] > dp[k])

              dp[k ^ arr[i]] = dp[k] + 1;

               res[k ^ arr[i]] = 1;

           }

       }

       int j = M - 1, k = n >> 1;

       while (dp[j] > k)

           --j;

       System.out.println (j);

   }

}

Explanation:

N=4,  A=[1,2,4,7] Khaled can choose the subset [7]. The xor of the elements in the subset is 7, and the number of elements in the subset is 1 which is less than       N/2.