And Or Union CodeChef Solution – Networking Funda

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.

Here, && denotes the Bitwise AND operation and || denotes the Bitwise OR operation.

Input Format

  • 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.

Output Format

For each test case, print a single line containing one integer — the last remaining element in array BB.


  • 1≤T≤1041≤T≤104
  • 2≤N≤1052≤N≤105
  • 0≤Ai≤1090≤Ai≤109
  • The sum of NN over all test cases does not exceed 2⋅1052⋅105.

Sample Input 1 

1 3
2 7 1
4 6 7 2

Sample Output 1 



Test Case 11: Array BB will be [A1&A2]=[1&3]=[1][A1&A2]=[1&3]=[1]. 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:

  1. Remove 22 and 00 from BB and insert 2|0=22|0=2 into it. Now, B=[1,2]B=[1,2].
  2. Remove 22 and 11 from BB and insert 2|1=32|1=3 into it. Now, B=[3]B=[3].

The last remaining element is thus 33.

Get More CodeChef Solution >>

Substring Minimum Function FizzBuzz Solution

Magical Planks Fizzbuzz Solution

Favourite String of Chef CodeChef Solution

Sum this up Code Chef Solution

Game between friends CodeChef Solution

Leave a Reply

error: Content is protected !!