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이 있는 요소가 적어도 하나 있어야 합니다. 나머지 요소는 해당 위치에 0 또는 1을 가질 수 있으며 중요하지 않습니다.

• 따라서 결과 하위 집합을 얻으려면 초기 배열을 탐색하십시오. 요소가 결과 하위 집합에 있어야 하는지 여부를 결정할 때 k의 이진 표현에 0인 위치가 있고 해당 요소의 해당 위치가 1인지 확인합니다. 그러한 위치가 있으면 해당 요소를 무시합니다. , 그렇지 않으면 결과 하위 집합에 포함합니다.

• k의 이진 표현에 0이고 요소의 해당 위치가 1인 위치가 있는지 확인하는 방법은 무엇입니까? 단순히 k와 해당 요소의 비트 OR을 취하십시오. k와 같지 않으면 그러한 위치가 존재하며 요소는 무시되어야 합니다. 비트 OR이 k이면 결과 하위 집합에 현재 요소를 포함합니다.

• 마지막 단계는 k의 해당 위치에 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