# PROBLEM LINK:

Practice

Contest: Division 1

Contest: Division 2

Contest: Division 3

Contest: Division 4

* Author:* jeevanjyot

*mexomerf, rivalq*

**Testers:***iceknight1093*

**Editorialist:**# DIFFICULTY:

TBD

# PREREQUISITES:

Basic bit manipulation

# PROBLEM:

You’re given an array A and an integer Y.

Determine the smallest non-negative integer X such that (A_1 \mid A_2 \mid \ldots \mid A_N \mid X) = Y or say that no such X exists.

# EXPLANATION:

Let Z = (A_1 \mid A_2 \mid \ldots \mid A_N). Computing Z is easy: just loop over the array.

We want to find X such that (Z\mid X) = Y.

Let’s look at each bit individually. For a fixed bit b,

- If b is set in Y, then at least one of X and Z must have b set.
- In particular, if Z has b set then we can leave it unset in X, since our aim is to minimize X.
- On the other hand, if Z doesn’t have b set, X
*must*have it set.

- If b is not set in Y, then neither X nor Z can have it set.
- In particular, if Z has b set then no valid X can exist, and the answer is immediately -1.

Repeating this process for each bit b tells us whether a valid X exists; and if it does, which bits to set in it to minimize its value.

While it’s possible to implement this by looping over values of b from 0 to 20, there’s a simpler way if you’re familiar with bitwise operations:

- Note that a valid X can exist only when Z is a submask of Y. This can be checked in several ways, for example,
`if ((Y & Z) == Z)`

. - When a valid X does exist, it contains exactly those bits that are set in Y but not Z, which is simply
`Y ^ Z`

since Z is a submask of Y (`^`

being xor here).

This gives us a very short implementation.

# TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

# CODE:

## Code (Python)

```
for _ in range(int(input())):
n, y = map(int, input().split())
a = list(map(int, input().split()))
orsum = 0
for x in a: orsum |= x
if (orsum & y) == orsum: print(y ^ orsum)
else: print(-1)
```