在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