সমস্যা বিবৃতি
n ধনাত্মক উপাদানগুলির একটি অ্যারে দেওয়া হয়েছে৷ আমাদের অ্যারে থেকে যেকোনো জোড়া উপাদান দ্বারা উৎপন্ন সর্বোচ্চ বিটওয়াইজ এবং মান খুঁজে বের করতে হবে।
উদাহরণ
যদি ইনপুট অ্যারে হয় {10, 12, 15, 18} তাহলে bitwise AND এর সর্বোচ্চ মান হল 12৷
অ্যালগরিদম
একক বিটে বিটওয়াইজ এবং অপারেশনের ফলাফল সর্বাধিক হয় যখন উভয় বিট 1 হয়। এই বৈশিষ্ট্যটি বিবেচনা করে −
- এমএসবি থেকে শুরু করুন এবং পরীক্ষা করুন যে আমাদের সেট মান সহ অ্যারের ন্যূনতম দুটি উপাদান আছে কিনা
- যদি হ্যাঁ, তাহলে সেই MSB আমাদের সমাধানের অংশ হবে এবং ফলাফলে যোগ করা হবে অন্যথায় আমরা সেটি বাতিল করে দেব
- একইভাবে, বিট পজিশনের জন্য MSB থেকে LSB (32 থেকে 1) পর্যন্ত পুনরাবৃত্তি করে আমরা সহজেই পরীক্ষা করতে পারি কোন বিটটি আমাদের সমাধানের অংশ হবে এবং আমাদের সমাধানে এই ধরনের সমস্ত বিট যোগ করতে থাকবে
উদাহরণ
আসুন এখন একটি উদাহরণ দেখি -
#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
