সমস্যা বিবরণ
N সংখ্যার একটি অ্যারে দেওয়া আছে। একই সংখ্যক সেট বিট (১-এর সংখ্যা) থাকা নম্বরগুলো যোগ করে যা ম্যাক্সিমাম সাম পাওয়া যায় সেটা বের করতে হবে।
উদাহরণ
ইনপুট: {2, 5, 8, 9, 10, 7} -> আউটপুট: ২৪
- 2: ১ সেট বিট
- 5: ২ সেট বিট
- 8: ১ সেট বিট
- 9: ২ সেট বিট
- 10: ২ সেট বিট
- 7: ৩ সেট বিট
২ সেট বিট والے: 5+9+10 = ২৪ (ম্যাক্সিমাম)
অ্যালগরিদম
- প্রতিটি এলিমেন্টের সেট বিট কাউন্ট করব।
- ৩২ সাইজের অ্যারে sum[32] নিব (ম্যাক্স ৩২ সেট বিট ধরে)।
- প্রতিটি এলিমেন্টকে তার সেট বিট কাউন্ট অনুযায়ী sum[bits] += arr[i] করব।
- sum অ্যারেতে ম্যাক্সিমাম মান বের করব।
উদাহরণ
#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
