在C ++中按位或等于k的最大子集

问题陈述

给定非负整数和整数k的数组，请找到按位或等于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

• 对于k的二进制表示形式中位等于0的所有位置，结果子集中所有元素的二进制表示形式中的对应位置必须为0

• 另一方面，对于k中的位等于1的位置，在对应位置必须至少有一个元素为1的元素。其余元素在该位置可以为0或1，这无关紧要。

• 因此，要获得结果子集，请遍历初始数组。在确定元素是否应位于结果子集中时，请检查k的二进制表示形式中是否有任何位置为0，并且该元素中的对应位置为1。如果存在这样的位置，则忽略该元素，否则将其包含在结果子集中。

• 如何确定k的二进制表示中是否存在一个位置为0且元素中相应位置为1的位置？只需对k与该元素进行按位或运算。如果不等于k，则存在这样的位置，因此必须忽略该元素。如果它们的按位或等于k，则将当前元素包括在结果子集中。

• 最后一步是确定是否至少有一个元素在k的对应位置中的位置与1对应的位置。

• 只需计算结果子集的按位或。如果等于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