【C++】ビット単位のORがkと等しくなる最大長の部分集合を求めるアルゴリズム

問題文

負でない整数からなる配列と整数 k が与えられたとき、ビット単位のOR（論理和）が k と等しくなる最大長の部分集合を求めます。

具体例

入力配列 = [1, 4, 2]、k = 3 の場合、出力は次のようになります。
[1, 2]
1 と 2 のビット単位のORは 3 に一致します。
これより長い（長さ3以上の）部分集合を作ることはできません。

アルゴリズムの考え方

まず、ビット単位のORには次のような基本的な性質があります。

0 OR 0 = 0
1 OR 0 = 1
1 OR 1 = 1

この性質から、以下のことが導けます。

• k の二進表現において 0 になっているビット位置では、結果となる部分集合に含まれるすべての要素の対応するビット位置も、必ず 0 でなければなりません。

• 一方、k のビットが 1 になっている位置については、部分集合内の少なくとも1つの要素がその位置で 1 を持っていれば十分です。残りの要素は 0 でも 1 でもどちらでも構いません。

• したがって、元の配列を先頭から走査し、各要素ごとに「k の二進表現で 0 となっているビット位置に、その要素が 1 を持っていないか」を確認します。該当するビット位置が存在する場合はその要素を無視し、存在しない場合は結果の部分集合に加えます。

• この判定は非常に簡単で、k とその要素のビット単位のORを計算するだけで済みます。ORの結果が k と等しくなければ、k が 0 の位置で要素が 1 になっている箇所が存在するため、その要素は除外します。逆にORの結果が k と等しければ、その要素を部分集合に含めて問題ありません。

• 最後のステップとして、k が 1 になっているビット位置に対して、部分集合内の少なくとも1つの要素が実際に 1 を持っているかどうかを確認する必要があります。

• これは、構築した部分集合全体のビット単位のORを計算すれば判定できます。結果が k と一致すればそれが最終的な答えであり、一致しなければ条件を満たす部分集合は存在しないということになります。

C++による実装例

#include <bits/stdc++.h>
using namespace std;
void getSubSet(int *arr, int n, int k){
    vector<int> v;
    for (int i = 0; i < n; i++) {
       if ((arr[i] | k) == k)
          v.push_back(arr[i]);
    }
    int ans = 0;
    for (int i = 0; i < v.size(); i++) {
       ans |= v[i];
    }
    if (ans != k) {
       cout << "Subset does not exist" << endl;
       return;
    }
    cout << "Result = ";
    for (int i = 0; i < v.size(); i++) {
       cout << v[i] << " ";
    }
    cout << endl;
}
int main(){
    int arr[] = { 1, 4, 2 };
    int k = 3;
    int n = sizeof(arr) / sizeof(arr[0]);
    getSubSet(arr, n, k);
    return 0;
}

実行結果

上記のプログラムをコンパイルして実行すると、次の出力が得られます。

Result = 1 2

計算量

このアルゴリズムは配列を一度だけ走査し、各要素に対して定数回のビット演算を行うため、時間計算量は O(n) です。また、候補となる要素を格納するために O(n) の補助領域を使用します。配列を並べ替える必要もなく、シンプルなビット演算だけで解ける点がこの手法の大きな特徴です。