সমস্যা বিবরণ
নন-নেগেটিভ ইন্টিজার অ্যারে এবং একটি ইন্টিজার k দেওয়া আছে। বিটওয়াইজ OR যেন k হয় এমন ম্যাক্সিমাম লেন্থের সাবসেট বের করতে হবে।
উদাহরণ
ইনপুট: arr = [1, 4, 2], k = 3 আউটপুট: [1, 2] ব্যাখ্যা: 1 OR 2 = 3। ২-এর চেয়ে বড় লেন্থের সাবসেট পাওয়া যাবে না।
অ্যালগরিদম
বিটওয়াইজ OR-এর প্রোপার্টি: 0|0=0, 1|0=1, 1|1=1।
- k-এর বাইনারি রিপ্রেজেন্টেশনে যেসব বিট ০, সাবসেটের সব এলিমেন্টের সেসব বিটও ০ হতে হবে।
- k-এর বিট ১ হলে সাবসেটে কমপক্ষে একটি এলিমেন্টের সেটা ১ থাকতে হবে।
- ট্রাভার্স করলে: (arr[i] | k) == k হলে এলিমেন্টটি সাবসেটে নিব।
- শেষে সাবসেটের OR করলে k হলে সাবসেটটি উত্তর, নাহলে "Subset does not exist"।
উদাহরণ
#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
