XOR-ORED solution codechef

XOR-ORED solution codechef

Given an array AA of NN non-negative integers, you can choose any non-negative integer XX and replace every element AiAi with (AiX)(Ai⊕X) Here,  denotes the bitwise XOR operation.

Using the above operation exactly once, your goal is to minimize the bitwise OR of the new array. In other words, find XX such that (A1X)(ANX)(A1⊕X)∨⋯∨(AN⊕X) is minimized, where  denotes the bitwise OR operation.

Find the value of XX and the minimum possible bitwise OR of the new array.

Input Format

  • The first line contains a single integer TT – the number of test cases. Then TT test cases follow.
  • The first line of each test case contains a single integer NN – the length of the array.
  • The next line contains NN integers A1,,ANA1,…,AN.

Output Format

For each test case, print two integers: XX and the minimum possible bitwise OR of the new array.

If there are multiple values of XX that achieve the minimum bitwise OR, print any of them.


  • 1T50001≤T≤5000
  • 1N1001≤N≤100
  • 0Ai1090≤Ai≤109

Sample Input 1 

4 6

Sample Output 1 

6 2


Here, if we take X=6X=6, then our expression would become (46)(66)=20=2(4⊕6)∨(6⊕6)=2∨0=2, which is the minimum possible.


Leave a Comment