PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: jeevanjyot
Testers: mexomerf, rivalq
Editorialist: iceknight1093
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)