Ddudda and Alarm Clocks

Let $Y$ be the OR value of a chosen non-empty set. We want the maximum possible $Y$ such that $Y \le M$.

Consider integer comparison in binary. For $Y \le M$, one of the following must hold.

• $Y = M$.
• At the highest bit $b$ where $Y$ and $M$ differ, $M$ has $1$ and has , while all higher bits are equal.

In the second case, lower bits below $b$ can be arbitrary. Therefore, every value $Y \le M$ is a bitwise submask of one of the following masks.

• $M$ itself.
• A value obtained by changing one set bit $b$ of $M$ to $0$ and changing all lower bits to $1$.

Call such a candidate mask $B$. For the final OR value to be a submask of $B$, every chosen $A_i$ must also be a submask of $B$. This is equivalent to

$$(A_i \operatorname{OR} B) = B$$

For a fixed $B$, if we OR all values satisfying this condition, the result is still a submask of $B$, so it is at most $B$ and therefore at most $M$. Also, bitwise OR never decreases when more values are chosen, so choosing all usable values is optimal for that $B$.

Thus, for every candidate mask $B$, compute

$$\bigvee_{\,(A_i \operatorname{OR} B) = B} A_i$$

The answer is the maximum among candidates where at least one value was usable. If no candidate allows any value, print $-1$.

There are at most $60$ candidate masks, and for each one we scan all $N$ values. The time complexity is $O(60N)$. Apart from the input array, the extra memory usage is $O(60)$.