เซตย่อยสูงสุดที่มีระดับบิต OR เท่ากับ k ใน C++

คำชี้แจงปัญหา

กำหนดอาร์เรย์ของจำนวนเต็มที่ไม่ติดลบและจำนวนเต็ม 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

• สำหรับตำแหน่งทั้งหมดในการแสดงเลขฐานสองของ k ที่มีบิตเท่ากับ 0 ตำแหน่งที่สอดคล้องกันในการแทนค่าไบนารีขององค์ประกอบทั้งหมดในเซตย่อยที่เป็นผลลัพธ์ควรเป็น 0

• ในทางกลับกัน สำหรับตำแหน่งใน k ที่มีบิตเท่ากับ 1 จะต้องมีองค์ประกอบอย่างน้อยหนึ่งตัวที่มี 1 อยู่ในตำแหน่งที่สอดคล้องกัน องค์ประกอบที่เหลือสามารถมี 0 หรือ 1 ในตำแหน่งนั้น ไม่สำคัญ

• ดังนั้น เพื่อให้ได้เซตย่อยที่เป็นผลลัพธ์ ให้สำรวจอาร์เรย์เริ่มต้น ขณะตัดสินใจว่าองค์ประกอบควรอยู่ในเซตย่อยที่เป็นผลลัพธ์หรือไม่ ให้ตรวจสอบว่ามีตำแหน่งใดในการแทนค่าไบนารีของ k ที่เป็น 0 และตำแหน่งที่สอดคล้องกันในองค์ประกอบนั้นคือ 1 หากมีตำแหน่งดังกล่าวอยู่ ให้เพิกเฉยต่อองค์ประกอบนั้น มิฉะนั้นจะรวมไว้ในเซตย่อยที่เป็นผลลัพธ์

• จะทราบได้อย่างไรว่ามีตำแหน่งอยู่ในการแสดงไบนารีของ k ซึ่งเป็น 0 และตำแหน่งที่สอดคล้องกันในองค์ประกอบคือ 1? เพียงแค่ใช้ OR ระดับบิตของ k และองค์ประกอบนั้น หากมันไม่เท่ากับ k แสดงว่ามีตำแหน่งดังกล่าวอยู่และองค์ประกอบนั้นจะต้องถูกละเว้น หากค่าระดับบิต OR เท่ากับ k ให้รวมองค์ประกอบปัจจุบันในชุดย่อยที่เป็นผลลัพธ์

• ขั้นตอนสุดท้ายคือการพิจารณาว่ามีอย่างน้อยหนึ่งองค์ประกอบที่มี 1 อยู่ในตำแหน่งที่มี 1 อยู่ในตำแหน่งที่สอดคล้องกันใน k

• เพียงคำนวณค่าบิต 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