समस्या कथन
n धनात्मक तत्वों का एक ऐरे दिया गया है। हमें ऐरे के किन्हीं दो तत्वों की पेयर द्वारा उत्पन्न अधिकतम बिटवाइज AND मान ढूंढना है।
उदाहरण
यदि इनपुट ऐरे है {10, 12, 15, 18} तो बिटवाइज AND का अधिकतम मान 12 है।
एल्गोरिदम
सिंगल बिट पर बिटवाइज AND ऑपरेशन का परिणाम अधिकतम होता है जब दोनों बिट्स 1 हों। इस गुण को ध्यान में रखते हुए:
- MSB से शुरू करें और जांचें कि क्या ऐरे के कम से कम दो तत्वों में सेट मान है।
- यदि हां, तो वह 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
