[1] Notation

For a non-negative integer \(X\), let the superior set of \(X\) be the set of non-negative integers \(Y\) such that \(X\ \mathrm{AND}\ Y=X\).

[2] Using binary search

To find the answer, one should maintain a variable \(\mathrm{ANS}\) that is initialized to \(0\) and do the following for each \(i=31,30,\dots,1,0\) in this order.

• If one of the elements of the superior set of $\mathrm{ANS}+2^i$ can be obtained as the bitwise $\mathrm{AND}$ of the chosen $K$ elements in at most $M$ operations, set $\mathrm{ANS}$ to $\mathrm{ANS}+2^i$.

This greedy method is valid because \(2^i > 2^0 + 2^1 + \dots + 2^{i-1}\) and thus one should get \(1\) in as high bits as possible.

[3] Solving the decision problem

Let us find the number of operations required to obtain one of the elements of the superior set of a non-negative integer \(X\).

We will find for each \(i\) (\(1 \le i \le N\)) the smallest integer \(B_i\) that is at least \(A_i\) and contained in the superior set of \(X\), and choose the \(K\) elements with the smallest \(B_i - A_i\).

To find the smallest integer \(B_i\) that is at least \(A_i\) and contained in the superior set of \(X\), do the following for each \(j=31,30,\dots,1,0\) in this order.

• If the $j$-th bit of $X$ is $1$, do nothing.
• If the $j$-th bit of $X$ is $0$, make it $1$ if the result of setting the $0$-th through $(j-1)$-th bits of $X$ to $1$ is less than $A_i$, and do nothing otherwise.

Now, we have found the number of operations required to make one of the elements of the superior set of a non-negative integer \(X\) in \(\mathrm{O}(N(\log N + \log A))\) time.

[4] Summary

The problem can therefore be solved in \(\mathrm{O}(N\log A(\log N + \log A))\) time.

Note that \(A_i\) can become as large as \(2^{31} - 2\).