# APPENDOR - Editorial

Author: jeevanjyot
Testers: mexomerf, rivalq
Editorialist: iceknight1093

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)

4 Likes