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 XOR of all the elements he chooses. Here, XOR denotes the bitwise XOR operation.

Question

Accepted Answer

Choose at most N/2 elements from an array A of N elements and find XOR of all the chosen elements.

Choose the N/2 largest elements to maximize the XOR value.
Use a priority queue to efficiently select the largest elements.
If N is small, brute force all possible combinations of N/2 elements.

Accepted Answer

#include using namespace std; int main () { int n; cin >> n; int arr[n]; for (int i = 0; i < n; i++) cin >> arr[i]; int M = 1 << 20; int dp[M]; char res[M]; for (int i = 1; i < M; i++) dp[i] = INT_MAX; 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--; cout << j; return 0; }

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 XOR of all the elements he chooses. Here, XOR denotes the bitwise XOR operation.

Top Infosys System Engineer interview questions & answers

Popular interview questions of System Engineer

Top HR questions asked in Infosys System Engineer