APPENDOR - Editorial

editorial
, ,
1

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)
5 Likes