Maximum Subset with Bitwise OR Equal to K ใน C++

ปัญหา

มีอาร์เรย์จำนวนเต็มบวกและ k หา Subset ที่ยาวที่สุดซึ่ง Bitwise OR ของทุกสมาชิกเท่ากับ k

ตัวอย่าง

Array = [1, 4, 2], k = 3
Output: [1, 2] (1|2 = 3)

อัลกอริทึม

1. คุณสมบัติ Bitwise OR: 0|0=0, 1|0=1, 1|1=1
2. สำหรับบิตที่ k เป็น 0: ทุกสมาชิกใน subset ต้องมีบิตนั้นเป็น 0
3. สำหรับบิตที่ k เป็น 1: ต้องมีอย่างน้อย 1 สมาชิกที่มีบิตนั้นเป็น 1
4. กรอง: เก็บเฉพาะ x ที่ (x | k) == k
5. ตรวจสอบ: OR ของ subset ที่กรองแล้ว ต้องเท่ากับ k

ตัวอย่างโค้ด C++

#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