इस समस्या में, हमें पूर्णांकों की एक सरणी arr[] दी गई है। हमारा कार्य C++ में आसन्न तत्वों पर विचार किए बिना सरणी में अधिकतम सेट बिट योग की गणना करने के लिए एक प्रोग्राम बनाना है।
समस्या विवरण - यहां, हमारे पास एक सरणी arr[] है। हमें प्रत्येक संख्या के लिए सेट बिट्स की संख्या ढूंढनी है। फिर, हम सरणी के आसन्न तत्वों में अधिकतम सेट बिट योग ढूंढेंगे। यानी a[i] + a[i+2] ... के लिए अधिकतम योग।
आइए एक उदाहरण से समस्या को समझते हैं,
इनपुट
arr[] = {1, 4, 6, 7}
आउटपुट
4
व्याख्या
तत्वों के बाइनरी रूप में सरणी:
arr[] = {01, 100, 101, 111} बिट काउंट सरणी = {1, 1, 2, 3}
वैकल्पिक बिट काउंट,
arr[0] + arr[2] = 1 + 2 = 3 arr[1] + arr[3] = 1 + 3 = 4
अधिकतम योग = 4।
समाधान दृष्टिकोण
इस समस्या को हल करने के लिए, हम बस संख्या में सेट बिट्स की संख्या ढूंढेंगे। और वैकल्पिक जोड़ी ढूंढेंगे जिसमें सेट बिट्स की अधिकतम संख्या हो।
अधिकतम योग 0 से शुरू होने वाली सरणी या 1 से शुरू होने वाली सरणी के लिए होगा। इसलिए, हमें केवल उन दोनों मामलों की जांच करने की आवश्यकता है।
हमारे समाधान के कार्य को दर्शाने वाला प्रोग्राम,
उदाहरण
#include<iostream>
using namespace std;
int countSetBit(int n){
int setBits = 0;
while(n) {
setBits++;
n = n & (n - 1);
}
return setBits;
}
int findMaxBitAltSubArray(int arr[], int n){
int EvenSum = countSetBit(arr[0]);
int OddSum = 0;
for (int i = 1; i < n; i++){
if(i % 2 == 0){
EvenSum += countSetBit(arr[i]);
} else {
OddSum += countSetBit(arr[i]);
}
}
if(EvenSum >= OddSum){
return EvenSum;
}
return OddSum;
}
int main() {
int arr[] = {1, 4, 6, 7};
int n = 4;
cout<<"The maximum set bit sum in the array without considering adjacent elements is "<<findMaxBitAltSubArray(arr, n);
return 0;
}
आउटपुट
The maximum set bit sum in the array without considering adjacent elements is 4
