Minimum AND xor OR

★★★★★

3.6

83 votes

1-D Array, Arrays, Data Structures, Operators, Sorting

Details

Submissions

Discussion

Editorial

Problem

You are given an array $A$ of $N$ integers. Determine the minimum value of the following expression for all valid $i,j$ :

$(A_i \ and \ A_j) \ xor \ (A_i \ or \ A_j)$ , where $i \ne j$ .

Input format

First line: A single integer $T$ denoting the number of test cases
For each test case:
- First line contains a single integer $N$ , denoting the size of the array
- Second line contains $N$ space-separated integers $A_1,A_2,...,A_n$

Output format

For each test case, print a single line containing one integer that represents the minimum value of the given expression

Constraints

$1 \le T \le 10^3\\ 1 \le N \le 10^5\\ 0 \le A_i \le 10^9$

Note: Sum of $N$ overall test cases does not exceed $10^6$

Time Limit: 1

Memory Limit: 256

Source Limit:

Explanation

For test case #1, we can select elements $2$ and $3$ , the value of the expression is $(2 \ and \ 3) \ xor \ (2 \ or \ 3) = 1$ , which is the minimum possible value. Another possible pair is 4 and 5.

For test case #2, we can select elements 4 and 7, the value of the expression is $(4 \ and \ 7) \ xor \ (4 \ or \ 7) = 3$ , which is the minimum possible value.