D. New Year's Problem

This can be solved easily with binary search on the min-max value.

auto possible = [&](int cutoff) -> bool {
        vector<bool> column(N, false);
        bool has_pair = false;
 
        for (int i = 0; i < M; i++) {
            int row_count = 0;
 
            for (int j = 0; j < N; j++) {
                row_count += P[i][j] >= cutoff;
                column[j] = column[j] || P[i][j] >= cutoff;
            }
 
            has_pair = has_pair || row_count >= 2;
        }
 
        return has_pair && accumulate(column.begin(), column.end(), 0) == N;
}    
int low = 0, high = INF;
 
while (low < high) {
   int mid = low + (high - low + 1) / 2;
 
   if (possible(mid))
        low = mid;
   else
        high = mid - 1;
}
 
cout << low << '\n';

While solving this in the contest, I wasn't able to come up with this approach. Rather I tried solving the same binary search function "possible" with a different approach and this lead me to a different version of the problem.

Task

Given an array of n positive integers $$$a_{1}$$$,$$$a_{2}$$$,...$$$a_{n}$$$ and an integer $$$m$$$ where $$$m$$$ is a power of 2. Determine the minimum number of numbers to be selected from the array so that their binary $$$OR$$$ will be $$$m-1$$$. If there doesn't exist a solution, output -1.

Input Format

$$$n$$$ $$$m$$$

$$$a_{1}$$$ $$$a_{2}$$$ ... $$$a_{n}$$$

Constraints

• $$$1$$$ < $$$n$$$ < $$$10^{5}$$$

• $$$1$$$ < $$$m$$$ < $$$2^{10}$$$

• $$$0$$$ <= $$$a_{i}$$$ <= $$$m$$$

Sample Input 1

3 32
10 21 31

Sample Output 1

1

Explanation

10 - 0  1  0  1  0
21 - 1  0  1  0  1
31 - 1  1  1  1  1
Selecting 31 will be enough.

Sample Input 2

5 32
9 25 27 10 21

Sample Output 2

2

Explanation

10 - 0  1  0  0  1
21 - 1  1  0  0  1
31 - 1  1  0  1  1
10 - 0  1  0  1  0
21 - 1  0  1  0  1

10 | 21 = 31. So answer will be 2.

I was not able to solve this and also tried searching for the same type of problem on the internet but failed to find one. If anyone has solved this before or has any thoughts of any complexity of the solution, please let me know.