Overview

When we want to compose each candidate’s skill set (bits) using OR to get exactly \(K\), we find the maximum number of people we can select. The key insight is that “anyone who has a bit not present in \(K\) can never be selected,” and we determine whether we can select all people who satisfy this condition.

Analysis

Key Observation

For the OR of a subset to be exactly \(K\), every selected person must not have any bit that doesn’t exist in \(K\).

• Let \(x\) be a candidate’s value.
• If \(x\) has even one bit where “that bit is 0 in \(K\) but 1 in \(x\),” then the moment we take the OR, that bit becomes 1, and the result exceeds (differs from) \(K\).
• Expressed as a formula, the necessary condition is “\((x \mid K) = K\).” (This means all 1-bits of \(x\) are contained within the 1-bits of \(K\).)

Therefore, only candidates satisfying [ (x \mid K) = K ] can be selected.

How to Maximize the Number of People?

Even if we include all “candidates satisfying the condition,” the OR result will not exceed \(K\) (since no extra bits are set). Since we want to maximize the number of people, including all of them is optimal if possible.

Then, we just need to verify whether the OR of all “candidates satisfying the condition” actually equals \(K\).

• If there are 0 candidates satisfying the condition → we can only form the empty set, but the problem requires a “non-empty subset,” so it’s impossible.
• If the OR of all qualifying candidates does not equal \(K\) → no subset can fill in the bits that should be set in \(K\), so it’s impossible.
• If the OR equals \(K\) → selecting everyone gives the maximum number of people.

Concrete Example

When \(K=10(=1010_2)\) and the candidates are \([2(0010), 8(1000), 1(0001)]\): - \(2|10=10\) → can be selected - \(8|10=10\) → can be selected - \(1|10=11\neq 10\) → cannot be selected (has a lower bit not in \(K\)) There are 2 selectable people, and the OR is \(2|8=10\), so the answer is 2.

Algorithm

1. For each \(A_i\), count only those satisfying \((A_i \mid K) = K\) as “selectable” (cnt).
2. Let orv be the OR of all selectable values.
3. If cnt==0 or orv != K, output -1.
4. Otherwise, the maximum number of people is all selectable candidates, so output cnt.

Complexity

• Time complexity: \(O(N)\) (each element is examined only once)
• Space complexity: \(O(1)\) (only a constant number of variables besides the input array)

Implementation Notes

• The selection condition is “the bits of \(A_i\) form a subset of the bits of \(K\),” so using (Ai | K) == K is concise.

• Although this is a problem asking for the “maximum number of people,” since there is a monotonicity property that “if selectable, choosing everyone is optimal,” neither DP nor exhaustive search is needed.

• Since the condition requires a non-empty subset, if the number of selectable people cnt is 0, the answer is always -1.

  Source Code

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return
    N, K = data[0], data[1]
    A = data[2:2+N]

    cnt = 0
    orv = 0
    for x in A:
        if (x | K) == K:
            cnt += 1
            orv |= x

    if cnt == 0 or orv != K:
        print(-1)
    else:
        print(cnt)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.