Problem: And Or Union CodeChef Solution
You are given an array AA consisting of NN integers.
From array AA, we create a new array BB containing all pairwise bitwise ANDs of elements from AA. That is, BB consists of N⋅(N−1)/2N⋅(N−1)/2 elements, each of the form Ai&AjAi&Aj for some 1≤i<j≤N1≤i<j≤N.
In array BB, we repeat the following process till there is only one element remaining:
- Let the current maximum and minimum element of array BB be XX and YY respectively.
- Remove XX and YY from array BB and insert X|YX|Y into it.
Determine the last remaining element in array BB.
- The first line of input contains a single integer TT, denoting the number of test cases. The description of TT test cases follows.
- The first line of each test case contains a single integer NN, denoting the number of elements in AA.
- The second line of each test case contains NN space-separated integers A1,A2,…,ANA1,A2,…,AN.
For each test case, print a single line containing one integer — the last remaining element in array BB.
- The sum of NN over all test cases does not exceed 2⋅1052⋅105.
Sample Input 1
3 2 1 3 3 2 7 1 4 4 6 7 2
Sample Output 1
1 3 6
Test Case 11: Array BB will be [A1&A2]=[1&3]=[A1&A2]=[1&3]=. There is only one element in BB so the answer is 11.
Test Case 22: Array BB will be [A1&A2,A1&A3,A2&A3]=[2&7,2&1,7&1]=[2,0,1][A1&A2,A1&A3,A2&A3]=[2&7,2&1,7&1]=[2,0,1].
Then, we do the following operations on BB:
- Remove 22 and 00 from BB and insert 2|0=22|0=2 into it. Now, B=[1,2]B=[1,2].
- Remove 22 and 11 from BB and insert 2|1=32|1=3 into it. Now, B=B=.
The last remaining element is thus 33.
Get More CodeChef Solution >>