समस्या कथन
N संख्याओं की एक सरणी दी गई है, कार्य उन संख्याओं को जोड़कर प्राप्त किए जा सकने वाले अधिकतम योग को ढूंढना है जिनमें समान संख्या में सेट बिट्स (set bits) हैं।
उदाहरण
यदि इनपुट सरणी {2, 5, 8, 9, 10, 7} है तो आउटपुट 24 होगा:
- 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 << "अधिकतम योग = " << maxSum(arr, n) << endl;
return 0;
}
आउटपुट
अधिकतम योग = 24
