Overview

This is a problem of finding the maximum number of members that can be selected from \(N\) candidates such that the bitwise OR of their skills is exactly \(K\).

Analysis

The key to this problem lies in narrowing down which candidates can potentially be on the team.

1. Filtering Candidates

If we want the OR of the entire team’s skills to be exactly \(K\), each member’s skill \(A_i\) added to the team must satisfy the following condition: - Every bit that is set in \(A_i\) must also be set in \(K\).

If \(A_i\) contains even a single bit that is 1 in \(A_i\) but 0 in \(K\), then the moment that person is added, that bit in the team’s overall OR becomes 1, making it impossible to ever match \(K\).

This condition can be concisely checked using bitwise operations as (A_i | K) == K.

2. Maximizing the Number of Members (Greedy Approach)

Our goal is to “maximize the number of members while making the OR exactly \(K\).” Even if we add all candidates satisfying the above condition to the team, the OR result will never exceed \(K\) (since no bit absent from \(K\) will become 1).

Therefore, “selecting all candidates that satisfy the condition” is the optimal strategy.

3. Final Verification

After selecting all candidates that satisfy the condition, we need to verify the following two points: - Is the team non-empty?: Since the problem states “non-empty subset,” at least one person must be selected. - Is the OR exactly \(K\)?: Even after gathering all people who satisfy the condition, if nobody possesses certain bits, the final OR may fall short of \(K\) (become less than \(K\)).

If both conditions are met, the number of selected people is the answer; otherwise, no valid team can be formed, so the answer is \(-1\).

Algorithm

1. Initialize a variable count to count the number of selectable people and a variable current_or to hold the OR of selected members, both to 0.
2. For each candidate’s skill \(A_i\), repeat the following:
   • If (A_i | K) == K:
     • Increment count by 1.
     • Add \(A_i\) to current_or using the OR operation (current_or |= A_i).
3. After the loop, if count > 0 and current_or == K, output count.
4. Otherwise, output -1.

Complexity

• Time Complexity: \(O(N)\)
  • Since we scan through the \(N\) candidates once, the processing completes in linear time with respect to the number of candidates.
• Space Complexity: \(O(N)\)
  • It is \(O(N)\) if all input values are stored, but it can be reduced to \(O(1)\) by reading and processing one value at a time.

Implementation Notes

• Bitwise condition check: (a_i | k) == k is a standard idiom for checking whether “\(a_i\) is a subset (bitwise subset) of \(k\).”

• Handling large integers: Since \(K\) and \(A_i\) can be as large as \(10^{18}\), depending on the language, you need to use a 64-bit integer type (in Python, this is handled automatically).

• Excluding the empty set: If no one satisfies the condition, current_or will be 0. If \(K=0\), this could lead to a false positive where “no one is selected yet the OR matches \(K\),” so the count > 0 check is important.

  Source Code

import sys

def solve():
    # 標準入力からすべてのデータを読み込み、スペースで分割します
    # N, K, A_1, A_2, ..., A_N の順で取得します
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # 候補者の人数 N と目標のスキルセット K を取得
    n = int(input_data[0])
    k = int(input_data[1])
    
    # 選べる候補者の数と、選んだメンバーのスキルのビット論理和（OR）を初期化
    count = 0
    current_or = 0
    
    # 各候補者のスキル A_i についてループ
    for i in range(n):
        a_i = int(input_data[2 + i])
        
        # A_i が目標値 K のサブセット（ビットの部分集合）であるか判定
        # すなわち、A_i に含まれるすべてのビットが K にも含まれているかを確認
        # (a_i | k) == k は a_i のビットが k に包含されていることを意味します
        if (a_i | k) == k:
            count += 1
            current_or |= a_i
            
    # 条件を満たす「空でない」部分集合が存在するか判定
    # 1. count > 0: 少なくとも一人の候補者が K のサブセットである
    # 2. current_or == k: 選んだ全員のスキルの OR がちょうど K に一致する
    # このとき、選べる最大の人数は count となります
    if count > 0 and current_or == k:
        print(count)
    else:
        # 条件を満たす部分集合が存在しない場合
        print(-1)

if __name__ == '__main__':
    solve()

---

This editorial was generated by gemini-3-flash-thinking.