সমস্যা বিবরণ
n সংখ্যক ধনাত্মক উপাদানের একটি অ্যারে দেওয়া আছে। আমাদের অ্যারে থেকে যেকোনো দুটি উপাদানের যুগল থেকে তৈরি সর্বোচ্চ বিটওয়াইজ AND মান বের করতে হবে।
উদাহরণ
যদি ইনপুট অ্যারে হয় {10, 12, 15, 18} তবে বিটওয়াইজ AND-এর সর্বোচ্চ মান হল ১২।
অ্যালগরিদম
বিটওয়াইজ AND অপারেশনের ফলাফল একক বিটের জন্য সর্বোচ্চ হয় যখন দুটি বিটই ১ হয়। এই বৈশিষ্ট্য বিবেচনা করে:
- MSB থেকে শুরু করে চেক করুন যে অ্যারেতে অন্তত দুটি উপাদান আছে কিনা যাদের সেই বিট সেট আছে।
- যদি হয়, তবে সেই MSB আমাদের সমাধানের অংশ হবে এবং রেজাল্টে যোগ হবে, অন্যথায় সেই বিট বাতিল করুন।
- এভাবেই MSB থেকে LSB (৩২ থেকে ১) পর্যন্ত বিট পজিশন için ইটারেট করে সহজেই বুঝা যায় কোন বিট আমাদের সমাধানের অংশ হবে এবং সেই সব বিট আমাদের সমাধানে যোগ করতে থাকব।
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
int checkBits(int* arr, int n, int pattern) {
int cnt = 0;
for (int i = 0; i < n; ++i) {
if ((pattern & arr[i]) == pattern) {
++cnt;
}
}
return cnt;
}
int getMaxBitwiseAnd(int* arr, int n) {
int result = 0;
int count;
for (int i = 31; i >= 0; --i) {
count = checkBits(arr, n, result | (1 << i));
if (count >= 2) {
result |= (1 << i);
}
}
return result;
}
int main() {
int arr[] = {10, 12, 15, 18};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Maximum bitwise AND = " << getMaxBitwiseAnd(arr, n) << endl;
return 0;
}
আউটপুট
Maximum bitwise AND = 12
