Tập hợp con tối đa có bitwise HOẶC bằng k trong C ++

Tuyên bố vấn đề

Cho một mảng các số nguyên không âm và một số nguyên k, hãy tìm tập con có độ dài lớn nhất với chiều dọc theo từng bit HOẶC bằng k.

Ví dụ

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.

Thuật toán

Dưới đây là các thuộc tính của bitwise OR -

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

• đối với tất cả các vị trí trong biểu diễn nhị phân của k với bit bằng 0, vị trí tương ứng trong biểu diễn nhị phân của tất cả các phần tử trong tập hợp con kết quả nhất thiết phải bằng 0

• Mặt khác, đối với các vị trí trong k có bit bằng 1, phải có ít nhất một phần tử có số 1 ở vị trí tương ứng. Các phần tử còn lại có thể có 0 hoặc 1 ở vị trí đó, điều đó không quan trọng.

• Do đó, để có được tập hợp con kết quả, hãy duyệt qua mảng ban đầu. Trong khi quyết định xem phần tử có nằm trong tập hợp con kết quả hay không, hãy kiểm tra xem có vị trí nào trong biểu diễn nhị phân của k là 0 và vị trí tương ứng trong phần tử đó là 1. Nếu tồn tại vị trí như vậy, thì hãy bỏ qua phần tử đó. , nếu không, hãy đưa nó vào tập hợp con kết quả.

• Làm thế nào để xác định xem có tồn tại một vị trí trong biểu diễn nhị phân của k là 0 và vị trí tương ứng trong một phần tử là 1 hay không? Đơn giản chỉ cần lấy OR theo từng bit của k và phần tử đó. Nếu nó không bằng k, thì tồn tại một vị trí như vậy và phần tử phải được bỏ qua. Nếu bitwise OR của chúng bằng k, thì hãy bao gồm phần tử hiện tại trong tập hợp con kết quả.

• Bước cuối cùng là xác định xem có ít nhất một phần tử có 1 ở vị trí với 1 ở vị trí tương ứng trong k.

• Đơn giản chỉ cần tính toán OR theo từng bit của tập hợp con kết quả. Nếu nó bằng k, thì đây là câu trả lời cuối cùng. Không tồn tại tập hợp con nào thỏa mãn điều kiện

Ví dụ

#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;
}

Đầu ra

Khi bạn biên dịch và thực thi chương trình trên. Nó tạo ra kết quả sau -

Result = 1 2