C++でビット単位のORがkに等しい最大サブセット

問題の説明

非負の整数の配列と整数kが与えられた場合、ビット単位のORがkに等しい最大長のサブセットを見つけます。

例

If given input array is = [1, 4, 2] and k = 3 then output is:
[1, 2]
The bitwise OR of 1 and 2 equals 3. It is not possible to obtain
a subset of length greater than 2.

アルゴリズム

以下はビットごとのORのプロパティです-

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

• ビットが0に等しいkのバイナリ表現のすべての位置について、結果のサブセットのすべての要素のバイナリ表現の対応する位置は、必ず0である必要があります

• 一方、ビットが1に等しいkの位置の場合、対応する位置に1が付いた要素が少なくとも1つ存在する必要があります。残りの要素は、その位置に0または1を設定できますが、問題ではありません。

• したがって、結果のサブセットを取得するには、初期配列をトラバースします。要素が結果のサブセットに含まれるべきかどうかを決定する際に、kのバイナリ表現に0であり、その要素の対応する位置が1である位置があるかどうかを確認します。そのような位置が存在する場合は、その要素を無視します。 、それ以外の場合は、結果のサブセットに含めます。

• kのバイナリ表現に0であり、要素内の対応する位置が1である位置が存在するかどうかを判断するにはどうすればよいですか？ kとその要素のビットごとのORを取るだけです。 kと等しくない場合、そのような位置が存在するため、要素は無視する必要があります。それらのビットごとのORがkに等しい場合は、結果のサブセットに現在の要素を含めます。

• 最後のステップは、kの対応する位置に1がある位置に1がある要素が少なくとも1つあるかどうかを判断することです。

• 結果のサブセットのビットごとのORを計算するだけです。それがkに等しい場合、これが最終的な答えです。それ以外の場合、条件を満たすサブセットは存在しません

例

#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