समस्या कथन
N संख्याओं की एक सरणी को देखते हुए, कार्य अधिकतम योग ज्ञात करना है जो समान संख्या में सेट बिट्स के साथ संख्याओं को जोड़कर प्राप्त किया जा सकता है
उदाहरण
यदि इनपुट ऐरे {2, 5, 8, 9, 10, 7} है तो आउटपुट 14 होगा -
-
2 में सेट बिट्स की संख्या 1 है
-
5 में सेट बिट्स की संख्या 2 है
-
8 में सेट बिट्स की संख्या 1 है
-
9 में सेट बिट्स की संख्या 2 है
-
10 में सेट बिट्स की संख्या 2 है
-
7 में सेट बिट्स की संख्या 3 है
तब (5 + 9 + 10) का योग 24 है जिसके सेट बिट्स की संख्या =2
एल्गोरिदम
-
सरणी में ट्रैवर्स करें और प्रत्येक तत्व के लिए सेट बिट्स की संख्या गिनें।
-
32 बिट्स के लिए एक ऐरे को इनिशियलाइज़ करें, यह मानते हुए कि संख्या में अधिकतम 32 सेट बिट्स हैं।
-
सरणी में पुनरावृति करें और सरणी तत्व को उस स्थिति में जोड़ें जो सेट बिट्स की संख्या को इंगित करता है।
-
पार करें और अधिकतम राशि ज्ञात करें और उसे वापस करें।
उदाहरण
#include <bits/stdc++.h>
using namespace std;
int bitCount(int n){
int count = 0;
while (n) {
count++;
n = n & (n - 1);
}
return count;
}
int maxSum(int arr[], int n){
int bits[n];
for (int i = 0; i < n; i++) {
bits[i] = bitCount(arr[i]);
}
int sum[32] = { 0 };
for (int i = 0; i < n; i++) {
sum[bits[i]] += arr[i];
}
int maximum = 0;
for (int i = 0; i < 32; i++) {
maximum = max(sum[i], maximum);
}
return maximum;
}
int main(){
int arr[] = {2, 5, 8, 9, 10, 7};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Maximum sum = " << maxSum(arr, n) << endl;
return 0;
} आउटपुट
जब आप उपरोक्त प्रोग्राम को संकलित और निष्पादित करते हैं। यह निम्नलिखित आउटपुट उत्पन्न करता है -
Maximum sum = 24