সমস্যা বিবৃতি
অ-ঋণাত্মক পূর্ণসংখ্যার একটি অ্যারে এবং একটি পূর্ণসংখ্যা k দেওয়া হলে, বিটওয়াইজ বা 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.
অ্যালগরিদম
নীচে বিটওয়াইজ বা −
এর বৈশিষ্ট্য রয়েছে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 এবং সেই উপাদানটির bitwise 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
